题解 P2774 【方格取数问题】
这题的二分图模型十分套路，是一道二分图带权最大独立集问题，有一个结论：二分图最大独立集=所有的点权-最小点覆盖数（用最少的点覆盖所有边）。
解释一下：因为所有的边已经被最小点覆盖点集中的点覆盖了，那么删掉这些点就是删掉所有边，剩下的点都是不联通且最大的。
而根据König定理，最小点覆盖=最大匹配。所以我们只要求最大匹配就好了。
（吐槽一下：这个定理网上证明并不多，而且许多证明都是用“显然”混过去了关键点，其他题解也没有说为什么是总点权-最小割，这里推荐Matrix67的证明）
这样我们就把横纵坐标奇偶性相同的点放在二分图的一侧，对相邻的点连一条容量为无限的边，二分图两侧的点分别向源点和汇点连一条容量为点权的边，之后跑一边最小割即可。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
struct node{
int x,y,next,z;
}w[2000001];
int tail,m,deep[110][110],head[110][110],a[110][110];
int heap,n,team[10010][2],cnt,tim,sum,ans,o[110][110];
int dx[5]={0,-1,0,1,0},dy[5]={0,0,-1,0,1};
inline void add(int x1,int y1,int x2,int y2,int z){
w[cnt].next=head[x1][y1];
w[cnt].x=x2; w[cnt].y=y2;
w[cnt].z=z; head[x1][y1]=cnt; cnt++;
}
inline bool bfs(){
heap=tail=1; tim++; o[0][0]=tim;
team[heap][0]=team[heap][1]=0;
deep[0][0]=1;
while (heap<=tail){
int x=team[heap][0],y=team[heap][1];
for (int i=head[x][y]; i!=-1; i=w[i].next){
if (w[i].z&&o[w[i].x][w[i].y]!=tim){
tail++; o[w[i].x][w[i].y]=tim;
deep[w[i].x][w[i].y]=deep[x][y]+1;
team[tail][0]=w[i].x; team[tail][1]=w[i].y;
}
}
heap++;
}
return (o[n+1][m+1]==tim);
}
int dfs(int x,int y,int l){
if ((!l)||(x==n+1&&y==m+1)) return l;
int used=0,minn,z;
for (int i=head[x][y]; i!=-1; i=w[i].next){
if (deep[w[i].x][w[i].y]==deep[x][y]+1&&w[i].z){
minn=min(l-used,w[i].z);
z=dfs(w[i].x,w[i].y,minn);
if (z){
w[i].z-=z; w[i^1].z+=z;
used+=z; if (used==l) break;
}
}
}
if (!used) deep[x][y]=0;
return used;
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++){
scanf("%d",&a[i][j]); sum+=a[i][j];
}
memset(head,-1,sizeof(head));
for (int i=1; i<=n; i++)
for (int j=1; j<=m; j++){
if (i%2==j%2){
add(0,0,i,j,a[i][j]);
add(i,j,0,0,0);
for (int k=1; k<=4; k++){
if (i+dx[k]<=0||i+dx[k]>n) continue;
if (j+dy[k]<=0||j+dy[k]>m) continue;
add(i,j,i+dx[k],j+dy[k],1e9);
add(i+dx[k],j+dy[k],i,j,0);
}
}
else{
add(i,j,n+1,m+1,a[i][j]);
add(n+1,m+1,i,j,0);
}
}
while (bfs()) ans+=dfs(0,0,1e9);
printf("%d\n",sum-ans);
return 0;
}