【网络流24题】方格取数问题
Description
在一个有m * n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。
Input
第1 行有2 个正整数m和n，分别表示棋盘的行数和列数。
接下来的m行，每行有n个正整数，表示棋盘方格中的数。
Output
将取数的最大总和输出
Sample Input
3 3
1 2 3
3 2 3
2 3 1
Sample Output
11
Hint
数据范围：
1<=N,M<=30
Source
网络流
二分图点权最大独立集， 网络最小割
思路：取出的点要互不相交，所以考虑用二分图来做。同时这是个裸的最大点权独立集独立集问题，可以用最小点权覆盖集来做。把点黑白染色,S->黑色点(w=黑色点方格上数字)，白色点->T(w=白色点方格上数字),同时黑色点->与他相邻的白色点(w=inf)。所有点权之和-流量即为答案
1 // It is made by XZZ 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #define File 6 #define Fname "grid" 7 using namespace std; 8 #define rep(a,b,c) for(rg int a=b;a<=c;a++) 9 #define drep(a,b,c) for(rg int a=b;a>=c;a--) 10 #define erep(a,b) for(rg int a=fir[b];a;a=nxt[a]) 11 #define il inline 12 #define rg register 13 #define vd void 14 #define t (dis[i]) 15 typedef long long ll; 16 il int gi(){ 17 rg int x=0;rg char ch=getchar(); 18 while(ch<'0'||ch>'9')ch=getchar(); 19 while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); 20 return x; 21 } 22 const int maxn=30*30+10,maxm=30*30*4+100,S=1,T=2; 23 int fir[maxn],nxt[maxm],dis[maxm],w[maxm],id=1; 24 int X[]={23333,0,0,1,-1},Y[]={23333,1,-1,0,0}; 25 il vd add(int a,int b,int c){ 26 nxt[++id]=fir[a],fir[a]=id,dis[id]=b,w[id]=c; 27 if(c)add(b,a,0); 28 } 29 int num[31][31]; 30 bool vis[maxn]; 31 il int ff(int now,int end,int minn){ 32 if(now==end)return minn; 33 vis[now]=1; 34 erep(i,now) 35 if(!vis[dis[i]]&&w[i]){ 36 rg int down=ff(dis[i],end,min(minn,w[i])); 37 if(down){w[i]-=down,w[i^1]+=down;return down;} 38 } 39 return 0; 40 } 41 int main(){ 42 freopen(Fname".in","r",stdin); 43 freopen(Fname".out","w",stdout); 44 int n=gi(),m=gi(),Id=2,sum=0,a=0; 45 rep(i,1,n)rep(j,1,m){ 46 num[i][j]=++Id; 47 sum+=a=gi(); 48 if((i+j)&1)add(S,num[i][j],a); 49 else add(num[i][j],T,a); 50 } 51 rep(i,1,n)rep(j,1,m)if((i+j)&1)rep(k,1,4) 52 if(num[i+X[k]][j+Y[k]])add(num[i][j],num[i+X[k]][j+Y[k]],666666666); 53 int flow,Flow=0; 54 while(flow=ff(S,T,666666666))Flow+=flow,memset(vis,0,sizeof vis); 55 printf("%d ",sum-Flow); 56 return 0; 57 }