«问题描述：
在一个有m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任
意2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。
«编程任务：
对于给定的方格棋盘，按照取数要求编程找出总和最大的数。
«数据输入：
由文件grid.in提供输入数据。文件第1 行有2 个正整数m和n，分别表示棋盘的行数
和列数。接下来的m行，每行有n个正整数，表示棋盘方格中的数。
«结果输出:
程序运行结束时，将取数的最大总和输出到文件grid.out中。
输入文件示例 输出文件示例
grid.in
3 3
1 2 3
3 2 3
2 3 1
grid.out
11
(1<=N,M<=30)
/* 二分图的最大点权独立集 先按照奇偶性把图分成一个二分图 因为定理：最大点权独立集=V-最小点权覆盖集=V-最小割 所以跑最大流就行了。 */ #include<cstdio> #include<iostream> #define N 1010 #define M 300010 #define inf 1000000000 using namespace std; int a[35][35],head[N],dis[N],q[N],n,m,cnt=1,S,T,ans; struct node{ int v,pre,f; };node e[M]; int ws(int x,int y){ return (x-1)*m+y; } void add(int u,int v,int f){ e[++cnt].v=v;e[cnt].f=f;e[cnt].pre=head[u];head[u]=cnt; e[++cnt].v=u;e[cnt].f=0;e[cnt].pre=head[v];head[v]=cnt; } bool bfs(){ for(int i=1;i<=T;i++)dis[i]=inf; int h=0,t=1;q[1]=S;dis[S]=0; while(h<t){ int now=q[++h]; for(int i=head[now];i;i=e[i].pre){ int v=e[i].v; if(e[i].f&&dis[v]>dis[now]+1){ dis[v]=dis[now]+1; if(v==T)return true; q[++t]=v; } } } return dis[T]!=inf; } int dinic(int now,int f){ if(now==T)return f; int rest=f; for(int i=head[now];i;i=e[i].pre){ int v=e[i].v; if(e[i].f&&dis[v]==dis[now]+1){ int t=dinic(v,min(rest,e[i].f)); if(!t)dis[v]=0; e[i].f-=t; e[i^1].f+=t; rest-=t; } } return f-rest; } int main(){ freopen("grid.in","r",stdin); freopen("grid.out","w",stdout); scanf("%d%d",&n,&m); S=0;T=n*m+1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ scanf("%d",&a[i][j]); ans+=a[i][j]; } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ if(i+j&1) add(ws(i,j),T,a[i][j]); else add(S,ws(i,j),a[i][j]); } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ if(i+j&1)continue; if(i-1>=1) add(ws(i,j),ws(i-1,j),inf); if(i+1<=n) add(ws(i,j),ws(i+1,j),inf); if(j-1>=1) add(ws(i,j),ws(i,j-1),inf); if(j+1<=m) add(ws(i,j),ws(i,j+1),inf); } while(bfs()) ans-=dinic(S,inf); printf("%d",ans); return 0; }