題意:給你一個矩陣,問從左上走到右下再從右下回到左上,每個點隻能走一次,問最大值是多少。
思路:一看就知道是費用流,但是在建圖這裡卡住了。因為一開始不知道怎麼從右下重新回到左上。
寫了很久建圖的過程,最後挂了 。然後參考了别人的圖,發現隻要在插入一個源點與起點連接配接,容量是2,費用是0,終點與彙點相連,容量是2,費用0。這樣就能控制來回兩次的問題。
關于建圖,将每個點拆成i , i + n * n .容量是1 ,費用是該點的值,容量1就能控制每個點隻走一次。當然起點和終點的容量得是2。
假設i和j可以相連,那麼将i + n * n 與j相連,容量是inf ,費用是0 ,當然這題我容量直接是2了,因為最大流就是2。
源點與起點相連,容量為2,費用為0.
終點與彙點相連,容量為2,費用為0.
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2005
#define inf 1<<28
#define LL(x) (x<<1)
#define RR(x) (x<<1|1)
#define REP(i,s,t) for(int i=(s);i<=(t);++i)
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
using namespace std;
inline void readint(int &ret)
{
char c;
do
{
c = getchar();
}
while(c < '0' || c > '9');
ret = c - '0';
while((c=getchar()) >= '0' && c <= '9')
ret = ret * 10 + ( c - '0' );
}
int Map[666][666] ;
int inmap(int x ,int y ,int n )
{
if(x >0 && x <= n && y > 0 && y <= n) return 1 ;
return 0 ;
}
int mx[2] = {0,1} ;
int my[2] = {1,0} ;
struct kdq
{
int s , e, l , c ,next ;
} ed[21111111] ;
int head[1111111] ,num ;
void add(int s ,int e ,int l ,int c )
{
ed[num].s = s ;
ed[num].e = e ;
ed[num].l = l ;
ed[num].c = c ;
ed[num].next = head[s] ;
head[s] = num ++ ;
ed[num].s = e ;
ed[num].e = s ;
ed[num].l = 0 ;
ed[num].c = -c ;
ed[num].next = head[e] ;
head[e] = num ++ ;
}
int S , T ;
int dis[1111111] ;
bool vis[1111111] ;
int qe[11111111] ;
int pre[1111111] ;
int path[1111111] ;
int spfa()
{
// REP(i,1,T) dis[i] = inf ;
mem(dis,-1) ;
dis[S] = 0 ;
vis[S] = 1 ;
int h = 0 ,t = 0 ;
qe[h ++ ] = S ;
while( h > t )
{
int tt = qe[t ++ ] ;
//cout << tt <<endl;
vis[tt] = 0 ;
for (int i = head[tt] ; ~i ; i = ed[i].next )
{
int e = ed[i].e ;
int l = ed[i].l ;
int c = ed[i].c ;
// cout << tt <<" " << e << " " << c << endl;
//cout << e << endl;
if(l > 0 &&dis[e] < dis[tt] + c)
{
pre[e] = tt ;
path[e] = i ;
dis[e] = dis[tt] + c ;
if(!vis[e])
{
vis[e] = 1 ;
qe[h ++ ] = e ;
}
}
}
}
return dis[T] != -1 ;
}
int MFMC()
{
int mic = 0 ;
while(spfa())
{
int flow = inf ;
for (int i = T ; i != S ; i = pre[i])
{
flow = min(flow ,ed[path[i]].l) ;
}
for (int i = T ; i != S ; i = pre[i])
{
ed[path[i]].l -= flow ;
ed[path[i] ^ 1].l += flow ;
}
mic += dis[T] * flow ;
}
return mic ;
}
void init()
{
mem(head,-1) ;
num = 0 ;
}
int main()
{
int n ;
while(cin >> n )
{
init() ;
S = 0 ;
T = n * n + n * n + 1 ;
REP(i,1,n)REP(j,1,n)readint(Map[i][j]) ;
REP(i,1,n)
{
REP(j,1,n)
{
add((i - 1 ) * n + j , n * n + (i - 1 ) * n + j , 1, Map[i][j]) ;//拆點,i -> i + n * n ,容量1,費用為該點值
REP(k,0,1)
{
int tx = i + mx[k] ;
int ty = j + my[k] ;
if(inmap(tx,ty,n))
{
add(n * n + (i - 1 ) * n + j , ( tx - 1 ) * n + ty ,2 ,0) ;//若兩點可達, i + n * n -> j ,容量為inf ,費用為0 .
}
}
}
}
add(1,1 + n * n , 1, Map[1][1]) ;//起點容量+1
add(n * n , n * n * 2 ,1,Map[n][n]) ;//終點容量+1
add(S,1,2,0) ;//源點到起點,容量2,費用0
add(n * n + n * n , T ,2,0) ;//終點到彙點,容量2,費用0
printf("%d\n",MFMC() - Map[1][1] - Map[n][n]) ;//因為起點和終點走了2次,是以要減去他的值,當然也可以在重新加邊的時候費用為0即可。
}
return 0 ;
}