题目大意：给定一张网格图，，每个点有一个代价和一个收益，如果选择了某个点将会付出这个代价，如果一个点被选择或周围的4个点都被选择那么就会获得这个收益，求最大收益
乍一看这个关系中既有【且】又有【或】，没有办法直接建图 但是我们有一个结论： 如果一个点周围的4个点都被选择，那么这个点一定不会被选择 这个结论几乎是显然的，因为如果周围的4个点都选择了的话，选择这个点一定不会产生任何贡献，不如不选
然后就好建图了
我们将网格图红黑染色，将红色的点反转源汇 对于一个点，如果这个点分到T集表示选择，那么： 如果这个点和周围的4个点都被划分到了S集，那么将会产生一个收益 如果这个点被划分到了T集，将会产生一个代价和一个收益 然后我们建出来的图就是这样的：
直接跑最小割就好了。
;int m,n,ans;namespace Max_Flow{struct abcd{int to,f,next;}table[1001001];int head[M],tot=1;int dpt[M];void Add(int x,int y,int z){table[++tot].to=y;table[tot].f=z;table[tot].next=head[x];head[x]=tot;}void Link(int x,int y,int z){Add(x,y,z);Add(y,x,0);}bool BFS(){static int q[M];int i,r=0,h=0;memset(dpt,-1,sizeof dpt);dpt[S]=1;q[++r]=S;while(r!=h){int x=q[++h];for(i=head[x];i;i=table[i].next)if(table[i].f&&!~dpt[table[i].to]){dpt[table[i].to]=dpt[x]+1;q[++r]=table[i].to;if(table[i].to==T)return true;}}return false;}int Dinic(int x,int flow){int i,left=flow;if(x==T) return flow;for(i=head[x];i&&left;i=table[i].next)if(table[i].f&&dpt[table[i].to]==dpt[x]+1){int temp=Dinic(table[i].to,min(left,table[i].f));left-=temp;table[i].f-=temp;table[i^1].f+=temp;}if(left) dpt[x]=-1;return flow-left;}}int main(){using namespace Max_Flow;int i,j,k,x;cin>>m>>n;for(i=1;i<=m;i++)for(j=1;j<=n;j++){scanf(“%d”,&x);if(i+j&1)Link(S,P1(i,j),x);elseLink(P1(i,j),T,x);}for(i=1;i<=m;i++)for(j=1;j<=n;j++){scanf(“%d”,&x);ans+=x;ans+=x;if(i+j&1)Link(S,P2(i,j),x),Link(P1(i,j),T,x);elseLink(P2(i,j),T,x),Link(S,P1(i,j),x);}dx[]={0,0,1,-1};dy[]={1,-1,0,0};for(i=1;i<=m;i++)for(j=1;j<=n;j++)if(i+j&1){Link(P2(i,j),P1(i,j),INF);for(k=0;k<4;k++){int xx=i+dx[k];int yy=j+dy[k];if(xx<=0||yy<=0||xx>m||yy>n)continue;Link(P2(i,j),P1(xx,yy),INF);}}else{Link(P1(i,j),P2(i,j),INF);for(k=0;k<4;k++){int xx=i+dx[k];int yy=j+dy[k];if(xx<=0||yy<=0||xx>m||yy>n)continue;Link(P1(xx,yy),P2(i,j),INF);}}while( BFS() )ans-=Dinic(S,INF);cout<<ans<<endl;return 0;}
志在山顶的人，不会贪念山腰的风景。
