题意：给定一个网格，每个网格有选取代价和占据收益。每个点被占据，需要满足以下两个条件至少一个条件：1.被选取 2.邻近方格都被选取（有公共边被称为邻近） 不一定要占据所有方格，求最大收益。
第一直观感受和文理分科那道题很像，这类肯定用最小割，这种题一般都这样搞，但是建图是个大问题。这道题建出来的图要满足，如果一个点要保留收益，那么要么自己的花费边被割，要么邻近的被割，怎么建呢？
考虑先黑白染色，拆点，然后我们S连向黑色，容量为花费，黑色向自己的分身连收益边，并且黑色向相邻的白色点的分身连INF，黑色分身向白色连INF，白色分身向自己连收益，白色向T连花费。
仔细观察我们发现，确实能满足要求。
这种题一般都是套路，我也不知道怎么就要这么建边，不过可以总结出一些东西，比如一旦有关系，两者之间都会连INF以确保能彼此影响又不会被最小割割中，然后花费和收益，拆点怎么安排就要看具体的题目了。
上代码（与原题的输入不一样，是自己写的）
#include<bits/stdc++.h> using namespace std; #define N 25 #define INF 1e9 #define id(x,y) ((x-1)*m+y) inline int read(){ int x=0,f=1; char a=getchar(); while(a<'0' || a>'9') {if(a=='-') f=-1; a=getchar();} while(a>='0' && a<='9') x=x*10+a-'0',a=getchar(); return x*f; } const int dir[4][2]={1,0,-1,0,0,1,0,-1}; int n,m,be[N][N],co[N][N],S,T,P,ans,d[1005],head[1005],cur[1005],cnt; bool vis[1005]; queue<int>q; struct edges{ int to,cap,flow,next; }e[2005]; inline void insert(int u,int v,int c){ e[cnt]=(edges){v,c,0,head[u]};head[u]=cnt++; e[cnt]=(edges){u,0,0,head[v]};head[v]=cnt++; } inline bool bfs(){ memset(vis,0,sizeof(vis)); vis[S]=1; d[S]=0; q.push(S); while(!q.empty()){ int x=q.front(); q.pop(); for(int i=head[x];i>=0;i=e[i].next){ if(!vis[e[i].to] && e[i].cap>e[i].flow) d[e[i].to]=d[x]+1,q.push(e[i].to),vis[e[i].to]=1; } } return vis[T]; } int dfs(int x,int a){ if(x==T || !a) return a; int f,flow=0; for(int& i=cur[x];i>=0;i=e[i].next){ if(d[e[i].to]==d[x]+1 && (f=dfs(e[i].to,min(a,e[i].cap-e[i].flow)))>0) e[i].flow+=f,flow+=f,e[i^1].flow-=f,a-=f; if(!a) break; } return flow; } inline int maxflow(){ int flow=0; while(bfs()){ for(int i=S;i<=T;i++) cur[i]=head[i]; flow+=dfs(S,INF); } return flow; } int main(){ memset(head,-1,sizeof(head)); n=read(); m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) be[i][j]=read(),ans+=be[i][j]; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) co[i][j]=read(); S=0; T=2*n*m+1; P=n*m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ int x,y; if((i+j)%2){ insert(S,id(i,j),co[i][j]),insert(id(i,j),id(i,j)+P,be[i][j]); for(int k=0;k<4;k++){ x=i+dir[k][0],y=j+dir[k][1]; if(x<1 || x>n || y<1 || y>m) continue; insert(id(i,j),id(x,y)+P,INF); insert(id(i,j)+P,id(x,y),INF); } } else insert(id(i,j)+P,id(i,j),be[i][j]),insert(id(i,j),T,co[i][j]); } ans-=maxflow(); printf("%d ",ans); return 0; }