考虑一开始把所有点都选了，再放弃一些点使得选择合法
考虑求出最小的放弃掉的价值
看到棋盘先黑白染色冷静一下
从 $S$ 向所有黑点连一条流量为点权的边，如果满流表示我放弃这个点的价值
从所有白点向所有 $T$ 连边，如果满流说明我放弃这个点的价值
从所有黑点 $x$ 向它四个方向的四个白点 $a,b,c,d$ 连边，流量 $INF$，表示不是边 $(S,x)$ 满流就是边 $(a,T),(b,T),(c,T),(d,T)$ 都满流（不是放弃 $x$ 就是放弃 $a,b,c,d$）
然后最小割就是最小放弃的价值
emm十分显然
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e5+7,M=4e6+7,INF=1e9+7,xx[4]={0,1,0,-1},yy[4]={1,0,-1,0}; int fir[N],from[M],to[M],val[M],cntt=1; inline void add(int a,int b,int c) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; val[cntt]=c; from[++cntt]=fir[b]; fir[b]=cntt; to[cntt]=a; val[cntt]=0; } int dep[N],Fir[N],S,T; queue <int> q; bool BFS() { for(int i=S;i<=T;i++) Fir[i]=fir[i],dep[i]=0; q.push(S); dep[S]=1; int x; while(!q.empty()) { x=q.front(); q.pop(); for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(dep[v]||!val[i]) continue; dep[v]=dep[x]+1; q.push(v); } } return dep[T]>0; } int DFS(int x,int mxf) { if(x==T||!mxf) return mxf; int fl=0,res; for(int &i=Fir[x];i;i=from[i]) { int &v=to[i]; if(dep[v]!=dep[x]+1||!val[i]) continue; if( res=DFS(v,min(mxf,val[i])) ) { mxf-=res; fl+=res; val[i]-=res; val[i^1]+=res; if(!mxf) break; } } return fl; } inline int Dinic() { int res=0; while(BFS()) res+=DFS(S,INF); return res; } int n,m,id[107][107],ans; inline bool pd(int i,int j) { return (i&1)^((j&1)^1); } int main() { n=read(); m=read(); int v,tx,ty; S=0,T=n*m+1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { v=read(); id[i][j]=(i-1)*m+j; ans+=v; if(pd(i,j)) add(S,id[i][j],v); else add(id[i][j],T,v); } for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) for(int k=0;k<4;k++) { tx=i+xx[k],ty=j+yy[k]; if(!pd(i,j)||tx<1||tx>n||ty<1||ty>m) continue; add(id[i][j],id[tx][ty],INF); } printf("%d",ans-Dinic()); return 0; }