题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=2132
题意:n*m的格子染色黑白,对于格子(i,j)染黑色则价值为A[i][j],白色为B[i][j]。若一个格子四周不同颜色的有x个,则额外的价值为x*C[i][j]。求最大价值。
思路:将格子黑白染色分成两个集合X和Y。S集合为X中的A和Y中的B,T为X中的B和Y中的A。相邻的连边为两个格子的C值之和。总权值减去最小割即是答案。
struct node { int v,cap,next; }; node edges[N]; int head[N],e; void add(int u,int v,int cap) { edges[e].v=v; edges[e].cap=cap; edges[e].next=head[u]; head[u]=e++; } void Add(int u,int v,int cap) { add(u,v,cap); add(v,u,0); } int pre[N],cur[N],num[N],h[N]; int Maxflow(int s,int t,int n) { int i; for(i=0;i<=n;i++) cur[i]=head[i],num[i]=h[i]=0; int u=s,Min,k,v; int ans=0; while(h[u]<n) { if(u==t) { Min=INF; for(i=s;i!=t;i=edges[cur[i]].v) { k=cur[i]; if(edges[k].cap<Min) Min=edges[k].cap,v=i; } ans+=Min; u=v; for(i=s;i!=t;i=edges[cur[i]].v) { k=cur[i]; edges[k].cap-=Min; edges[k^1].cap+=Min; } } for(i=cur[u];i!=-1;i=edges[i].next) { if(edges[i].cap>0&&h[u]==h[edges[i].v]+1) break; } if(i!=-1) { cur[u]=i; pre[edges[i].v]=u; u=edges[i].v; } else { if(--num[h[u]]==0) break; k=n; cur[u]=head[u]; for(i=head[u];i!=-1;i=edges[i].next) { if(edges[i].cap>0&&h[edges[i].v]<k) { k=h[edges[i].v]; } } num[k+1]++; h[u]=k+1; if(u!=s) u=pre[u]; } } return ans; } int n,m,a[105][105],b[105][105]; int dx[]={0,0,1,-1}; int dy[]={1,-1,0,0}; int main() { RD(n,m); int i,j,k=0; FOR1(i,n) FOR1(j,m) a[i][j]=++k; clr(head,-1); int ans=0; int s=0,t=n*m+1; FOR1(i,n) FOR1(j,m) { RD(k); ans+=k; if((i+j)&1) Add(s,a[i][j],k); else Add(a[i][j],t,k); } FOR1(i,n) FOR1(j,m) { RD(k); ans+=k; if(!((i+j)&1)) Add(s,a[i][j],k); else Add(a[i][j],t,k); } FOR1(i,n) FOR1(j,m) RD(b[i][j]); int x,y; FOR1(i,n) FOR1(j,m) FOR0(k,4) { x=i+dx[k]; y=j+dy[k]; if(x>=1&&x<=n&&y>=1&&y<=m) { ans+=b[i][j]; Add(a[i][j],a[x][y],b[i][j]+b[x][y]); } } ans-=Maxflow(s,t,t+1); PR(ans); }