hdu 1569 方格取数(2)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1569
题目大意：求在n*m的棋盘中选出两两不相邻的数，使得和最大。
题目思路：按国际象棋黑白染色,源点到黑点容量为数字,黑点到它周围的白点容量为无穷,白点到汇点容量为数字,最后答案为总值减去最小割（摘自网上）。
#include<stdio.h>#include<stdlib.h>#include<string.h>#include<string>#include<queue>#include<algorithm>#include<vector>#include<stack>#include<list>#include<iostream>#include<map>using namespace std;#define inf 0x7f3f3f3f#define Max 50000int max(int a,int b){ return a>b?a:b;}int min(int a,int b){ return a<b?a:b;}int dis[Max],gap[Max],pre[Max],cur[Max],p[Max],sum;int d[4][2]={0,1,1,0,0,-1,-1,0};int mp[220][220];int n,m,s,t,eid;struct node { int to,next,c; }e[8*Max];void addedge(int u,int v,int c){ e[eid].to=v; e[eid].c=c; e[eid].next=p[u]; p[u]=eid++;}void ISAP(int st,int ed,int n,int count) ///起点，终点，顶点数{ memset(dis, 0, sizeof(dis)); memset(gap, 0, sizeof(gap)); gap[0]=n; memcpy(cur, p, sizeof(p)); ///memcpy! int i,flag,v,u=pre[st]=st,maxflow=0,aug=inf; //puts("akk"); while(dis[st] < n) { for(flag=0,i=cur[u];i!=-1; i=e[i].next) /// cur[u] if(e[i].c&& dis[u] == dis[e[i].to]+1) { flag = 1; break; } if(flag) { if(aug > e[i].c) aug = e[i].c; v = e[i].to; pre[v] = u; cur[u] = i; u = v; if(u == ed) { for(u=pre[u]; 1;u=pre[u]) ///notice! { e[cur[u]].c -= aug; e[cur[u]^1].c += aug; if(u==st) break; // puts("akkk"); } maxflow += aug; aug = inf; } } else { int minx = n; for(i=p[u]; i!=-1; i=e[i].next) if(e[i].c&& dis[e[i].to]<minx) { minx = dis[e[i].to]; cur[u] = i; } if(--gap[dis[u]] == 0) break; dis[u] = minx+1; gap[dis[u]]++; u = pre[u]; } } // printf("Case %d:\n%d\n",count,maxflow); printf("%d\n",sum-maxflow);}int main(){ int m,n,t,count=1; int u,v,c,i,j,k,x,y; while( scanf("%d%d",&n,&m)!=EOF) { eid=0; memset(p,-1,sizeof(p)); sum=0; for(i=0;i<n;i++) for(j=0;j<m;j++) { scanf("%d",&mp[i][j]); sum+=mp[i][j]; } for(i=0;i<n;i++) for(j=0;j<m;j++) { if((i+j)%2==0) { addedge(n*m,i*m+j,mp[i][j]); addedge(i*m+j,n*m,0); for(k=0;k<4;k++) { x=i+d[k][0]; y=j+d[k][1]; if(x>=0&&y>=0&&x<n&&y<m) { addedge(i*m+j,x*m+y,inf); addedge(x*m+y,i*m+j,0); } } } else { addedge(i*m+j,n*m+1,mp[i][j]); addedge(n*m+1,i*m+j,0); } } // printf("%d\n",eid); ISAP(n*m,n*m+1,n*m+2,count++); // printf("%d\n") }}