可以看出原图是一个二分图
调用最大独立集模板即可
#include<bits/stdc++.h> using namespace std; const int N=10005,M=20005,inf=1000000; int n,m,S,T; int get(int x,int y){ return x*m+y-1; } int fb(int x,int y){ return (x+y)&1; } struct oppo{ int to,nex,s; }rod[M]; int head[N],tot; void add(int from,int to,int s) { rod[tot].to=to; rod[tot].s=s; rod[tot].nex=head[from]; head[from]=tot++; } void link(int from,int to,int s) { add(from,to,s); add(to,from,0); } int ans; int d[N],cur[N]; bool bfs() { queue< int > v; memset(d,-1,sizeof(d)); d[S]=0,cur[S]=head[S]; v.push(S); while(v.size()){ int lxl=v.front();v.pop(); for(int i=head[lxl];~i;i=rod[i].nex){ int to=rod[i].to; if(d[to]==-1&&rod[i].s){ d[to]=d[lxl]+1; cur[to]=head[to]; if(to==T) return 1; v.push(to); } } } return 0; } int find(int x,int low) { if(x==T) return low; int all=0; for(int i=cur[x];~i;i=rod[i].nex){ cur[x]=i; int to=rod[i].to; if(d[to]==d[x]+1&&rod[i].s){ int t=find(to,min(rod[i].s,low-all)); if(!t) d[to]=-1; rod[i].s-=t; rod[i^1].s+=t; all+=t; } if(all==low) break; } return all; } int dinic() { int ans=0,r; while(bfs()) while(r=find(S,inf)) ans+=r; return ans; } int main() { memset(head,-1,sizeof(head)); cin>>n>>m; S=0,T=get(n,m)+1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ int t; scanf("%d",&t); ans+=t; if(fb(i,j)){ link(S,get(i,j),t); if(i!=n) link(get(i,j),get(i+1,j),inf); if(i!=1) link(get(i,j),get(i-1,j),inf); if(j!=m) link(get(i,j),get(i,j+1),inf); if(j!=1) link(get(i,j),get(i,j-1),inf); } else link(get(i,j),T,t); } cout<<ans-dinic()<<"\n"; return 0; }