题意:
一块土地可以纵横划分为N×M块小区域。于第i行第j列的区域,建造商业区将得到Aij收益,建造工业区将得到Bij收益。而如果区域(i,j)相邻(相邻是指两个格子有公共边)有K块(显然K不超过4)类型不同于(i,j)的区域,则这块区域能增加k×Cij收益。已知收益矩阵A,B,C,求收益最大值。
题解:
因为附加收益不是两两之间的,所以不用考虑除以2的问题。由于需要两块土地属性不同,所以对整个棋盘进行黑白染色。如果一块土地A为黑色,则s->A :c[A商] A->T:c[A工],如果为白色则反之s->A:c[A工] A->T:c[A商],对于相邻的AB A<->B c[A合]+c[B合]。最后答案是所有收益和减最小割。
代码:
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define visit(i,j) for(int i=g[j];i!=-1;i=es[i].n)
#define INF 0x3fffffff
using namespace std; struct e{int t,c,n;}; e es[]; int ess,g[];
inline void pe(int f,int t,int c){es[++ess]=(e){t,c,g[f]}; g[f]=ess; es[++ess]=(e){f,,g[t]}; g[t]=ess;}
inline void pe2(int f,int t,int c){es[++ess]=(e){t,c,g[f]}; g[f]=ess; es[++ess]=(e){f,c,g[t]}; g[t]=ess;}
inline void init(){ess=-; memset(g,-,sizeof(g));}
queue <int> q; int h[];
bool bfs(int s,int t){
while(! q.empty())q.pop(); memset(h,-,sizeof(h)); q.push(s); h[s]=;
while(! q.empty()){
int x=q.front(); q.pop();
visit(i,x)if(es[i].c&&h[es[i].t]==-){h[es[i].t]=h[x]+; q.push(es[i].t);}
}
if(h[t]==-)return ;else return ;
}
int dfs(int x,int t,int f){
if(x==t)return f; int u=;
visit(i,x)if(es[i].c&&h[es[i].t]==h[x]+){
int w=dfs(es[i].t,t,min(f,es[i].c));
f-=w; u+=w; es[i].c-=w; es[i^].c+=w; if(f==)return u;
}
if(!u)h[x]=-; return u;
}
int dinic(int s,int t){int f=; while(bfs(s,t))f+=dfs(s,t,INF); return f;}
int a1[][],a2[][],a3[][],tot,n,m,s,t; bool col[][];
inline int cg(int x,int y){return (x-)*m+y;}
int main(){
scanf("%d%d",&n,&m); tot=;
inc(i,,n)inc(j,,m)scanf("%d",&a1[i][j]),tot+=a1[i][j];
inc(i,,n)inc(j,,m)scanf("%d",&a2[i][j]),tot+=a2[i][j];
inc(i,,n)inc(j,,m)scanf("%d",&a3[i][j]);
s=; t=n*m+; init();inc(i,,n)inc(j,,m){col[i][j]=(i+j)&;}
inc(i,,n)inc(j,,m){
if(col[i][j])pe(s,cg(i,j),a1[i][j]),pe(cg(i,j),t,a2[i][j]);else pe(s,cg(i,j),a2[i][j]),pe(cg(i,j),t,a1[i][j]);
if(i!=n)pe2(cg(i,j),cg(i+,j),a3[i][j]+a3[i+][j]),tot+=(a3[i][j]+a3[i+][j]);
if(j!=m)pe2(cg(i,j),cg(i,j+),a3[i][j]+a3[i][j+]),tot+=(a3[i][j]+a3[i][j+]);
}
printf("%d",tot-dinic(s,t));
return ;
}
20160324