题意
在一个有 m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。
想法
我们将问题转化为：一开始所有格子都选，之后去掉价值和最少的一些格子使剩下的格子合法。
将方格黑白染色，白格子连向S，黑格子连向T，边权为这个格子的值（也就是说将格子转移到边上）。
相邻的黑白格子间连INF的边。（这样每条从S到T的路径都为 S->白格子->黑格子->T ， 这两个格子不能同时选，S->白格子 与 黑格子->T 间必然会割掉一条边）
注意一个小trick:对于永远不被割掉的边，边权设为INF
这样跑完最小割后，剩下的格子是合法的。而最小割的容量便为去掉的那些格子的价值和。
代码
#include<cstdio>
#include<iostream>
#include<algorithm>#define INF 2000000000using namespace std;typedef long long ll;
const int N = 10005;struct node{int v,f;node *next,*rev;
}pool[N*20],*h[N];
int cnt;void addedge(int u,int v,int f){node *p=&pool[++cnt],*q=&pool[++cnt];p->v=v;p->next=h[u];h[u]=p; p->f=f;p->rev=q;q->v=u;q->next=h[v];h[v]=q; q->f=0;q->rev=p;
}int S,T;
int que[N],level[N];
bool bfs(){int head=0,tail=0,u,v;for(int i=S;i<=T;i++) level[i]=-1;level[S]=1; que[tail++]=S;while(head<tail){u=que[head++];for(node *p=h[u];p;p=p->next)if(p->f && level[v=p->v]==-1){level[v]=level[u]+1;que[tail++]=v; }if(level[T]!=-1) return true;} return false;
}
int find(int u,int f){int v,s=0,t;if(u==T) return f;for(node *p=h[u];p;p=p->next)if(p->f && s<f && level[v=p->v]==level[u]+1){t=find(v,min(f-s,p->f));if(t){s+=t;p->f-=t;p->rev->f+=t; }}if(!s) level[u]=-1;return s;
}
ll dinic(){ll f=0;while(bfs()) f+=find(S,INF);return f;
}int n,m;
int val[105][105];bool check(int x,int y){if(x<1 || y<1 || x>n || y>m) return false;return true;
}int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) scanf("%d",&val[i][j]);ll sum=0;S=0; T=n*m+1;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){sum=sum+val[i][j];if((i+j)&1) addedge(S,(i-1)*m+j,val[i][j]);else{addedge((i-1)*m+j,T,val[i][j]);continue; }for(int dx=-1;dx<2;dx++)for(int dy=-1;dy<2;dy++)if(dx*dy==0 && dx!=dy){int t1=i+dx,t2=j+dy;if(check(t1,t2)) addedge((i-1)*m+j,(t1-1)*m+t2,INF); }}sum-=dinic();printf("%lld\n",sum);return 0;
}