emm........仔细一看，这不是最大权闭合子图的题吗！
取一个点$(x,y)$，限制条件是同时取$(x,y+1),(x,y-1),(x+1,y),(x-1,y)$，只不过权值取负而已
于是我们把图分为黑点和白点，同颜色点之间不相邻，不同颜色的点相邻（如将$(x+y)%2==1$的点记为黑点）
假装把白点的权值都看成负的
记$link(p,q,val)$为$p$向$q$连一条$val$的边（包括反向边）
蓝后根据最大权闭合子图的套路
对于黑点$p$与相邻的白点$q$
$link(S,p,val_p)$
$link(p,q,inf)$
$link(q,T,val_q)$（$val_q$不取负）
蓝后就可以愉快地跑最小割辣
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; #define N 100005 #define inf 1000000000 const int d1[4]={1,0,-1,0}; const int d2[4]={0,1,0,-1}; int n,m,d[N],cur[N],tot,S,T; bool vis[N]; queue <int> h; int cnt=1,hd[N],nxt[N],ed[N],poi[N],val[N]; inline void adde(int x,int y,int v){ nxt[ed[x]]=++cnt, hd[x]=hd[x]?hd[x]:cnt, ed[x]=cnt, poi[cnt]=y, val[cnt]=v; } inline void link(int x,int y,int v){adde(x,y,v),adde(y,x,0);} inline int id(int x,int y){return (x-1)*m+y;} bool bfs(){ memset(vis,0,sizeof(vis)); h.push(S); vis[S]=1; while(!h.empty()){ int x=h.front(); h.pop(); for(int i=hd[x];i;i=nxt[i]){ int to=poi[i]; if(!vis[to]&&val[i]>0) vis[to]=1,d[to]=d[x]+1,h.push(to); } }return vis[T]; } int dfs(int x,int a){ if(x==T||a==0) return a; int F=0,f; for(int &i=cur[x];i;i=nxt[i]){ int to=poi[i]; if(d[to]==d[x]+1&&(f=dfs(to,min(a,val[i])))>0) a-=f,F+=f,val[i]-=f,val[i^1]+=f; if(!a) break; }return F; } int dinic(){ int re=0; while(bfs()){ for(int i=1;i<=T;++i) cur[i]=hd[i]; re+=dfs(S,inf); }return re; } void draw(int x,int y){ int p=id(x,y),w; scanf("%d",&w); tot+=w; if((x+y)&1){//不要重复连边 link(S,p,w); for(int i=0;i<4;++i){ int r1=x+d1[i],r2=y+d2[i]; if(r1>0&&r1<=n&&r2>0&&r2<=m) link(p,id(r1,r2),inf); } }else link(p,T,w); } int main(){ scanf("%d%d",&n,&m); S=n*m+1; T=S+1; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) draw(i,j); printf("%d",tot-dinic()); return 0; }