bzoj 2132: 圈地计划

Description

最近房地产商GDOI(Group of Dumbbells Or Idiots)从NOI(Nuts Old Idiots)手中得到了一块开发土地。据了解，这块土地是一块矩形的区域，可以纵横划分为N×M块小区域。GDOI要求将这些区域分为商业区和工业区来开发。根据不同的地形环境，每块小区域建造商业区和工业区能取得不同的经济价值。更具体点，对于第i行第j列的区域，建造商业区将得到Aij收益，建造工业区将得到Bij收益。另外不同的区域连在一起可以得到额外的收益，即如果区域(I,j)相邻（相邻是指两个格子有公共边）有K块（显然K不超过4）类型不同于(I,j)的区域，则这块区域能增加k×Cij收益。经过Tiger.S教授的勘察，收益矩阵A,B,C都已经知道了。你能帮GDOI求出一个收益最大的方案么？

Input

输入第一行为两个整数，分别为正整数N和M，分别表示区域的行数和列数；第2到N+1列，每行M个整数，表示商业区收益矩阵A；第N+2到2N+1列，每行M个整数，表示工业区收益矩阵B；第2N+2到3N+1行，每行M个整数，表示相邻额外收益矩阵C。第一行，两个整数，分别是n和m（1≤n，m≤100）；

任何数字不超过1000”的限制

Output

输出只有一行，包含一个整数，为最大收益值。

Sample Input

3 3
1 2 3
4 5 6
7 8 9
9 8 7
6 5 4
3 2 1
1 1 1
1 3 1
1 1 1

Sample Output

81
【数据规模】
对于100%的数据有N,M≤100

题解：

类似于为了博多一题，同为总和减不合法，此题唯一变换就是不同改为相同，所以只需调换顺序即可

但是此题对于我这种蒟蒻来说，需要get新技能哈，怎么保证相邻连起来不矛盾呢？

这里用到二分图染色，对于网格图的都普遍用到此法....然后就直接黑向白或者白向黑连边即可.

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <cmath>
 6 #define id(x,y) (((x)-1)*m+(y))
 7 using namespace std;
 8 const int N=105,P=100005,M=2000005,inf=2e9;
 9 int map[N][N],n,m;bool color[N][N];
10 int head[P],num=1;
11 struct Lin{
12     int next,to,dis;
13 }a[M];
14 void makecolor(int x,int y)
15 {
16     int k=color[x][y]^1;
17     if(x<n && !color[x+1][y])color[x+1][y]=k,makecolor(x+1,y);
18     if(y<m && !color[x][y+1])color[x][y+1]=k,makecolor(x,y+1);
19 }
20 void init(int x,int y,int dis){
21     a[++num].next=head[x];a[num].to=y;a[num].dis=dis;head[x]=num;
22 }
23 void addedge(int x,int y,int dis){
24     init(x,y,dis);init(y,x,0);
25 }
26 int S=0,T,dep[P],q[P];
27 bool bfs(){
28     memset(dep,0,sizeof(dep));
29     int t=0,sum=1,u,x;
30     dep[S]=1;q[1]=S;
31     while(t!=sum){
32         x=q[++t];
33         for(int i=head[x];i;i=a[i].next){
34             u=a[i].to;
35             if(a[i].dis<=0 || dep[u])continue;
36             dep[u]=dep[x]+1;q[++sum]=u;
37         }
38     }
39     return dep[T];
40 }
41 int dfs(int x,int flow){
42     if(x==T || !flow)return flow;
43     int tot=0,u,tmp;
44     for(int i=head[x];i;i=a[i].next){
45         u=a[i].to;
46         if(dep[u]!=dep[x]+1 || a[i].dis<=0)continue;
47         tmp=dfs(u,min(flow,a[i].dis));
48         a[i].dis-=tmp;a[i^1].dis+=tmp;
49         tot+=tmp;flow-=tmp;
50         if(!flow)break;
51       }
52     if(!tot)dep[x]=0;
53     return tot;
54 }
55 int maxflow(){
56     int tot=0,tmp;
57     while(bfs()){
58         tmp=dfs(S,inf);
59         while(tmp)tot+=tmp,tmp=dfs(S,inf);
60     }
61     return tot;
62 }
63 int main()
64 {
65     scanf("%d%d",&n,&m);T=n*m+1;
66     color[1][1]=true;makecolor(1,1);
67     int x,ans=0;
68     for(int i=1;i<=n;i++)
69     for(int j=1;j<=m;j++){
70         scanf("%d",&x);ans+=x;
71         if(color[i][j])addedge(S,id(i,j),x);
72         else addedge(id(i,j),T,x);
73     }
74     for(int i=1;i<=n;i++)
75     for(int j=1;j<=m;j++){
76         scanf("%d",&x);ans+=x;
77         if(!color[i][j])addedge(S,id(i,j),x);
78         else addedge(id(i,j),T,x);
79     }
80     for(int i=1;i<=n;i++)
81     for(int j=1;j<=m;j++)
82     scanf("%d",&map[i][j]),ans+=(map[i][j]<<2);
83     for(int i=1;i<=n;i++)
84         for(int j=1;j<=m;j++){
85             if(color[i][j]){
86                 if(j>1)addedge(id(i,j-1),id(i,j),map[i][j]+map[i][j-1]),addedge(id(i,j),id(i,j-1),map[i][j]+map[i][j-1]);
87                 if(i>1)addedge(id(i-1,j),id(i,j),map[i][j]+map[i-1][j]),addedge(id(i,j),id(i-1,j),map[i][j]+map[i-1][j]);
88                 if(i<n)addedge(id(i+1,j),id(i,j),map[i][j]+map[i+1][j]),addedge(id(i,j),id(i+1,j),map[i][j]+map[i+1][j]);
89                 if(j<m)addedge(id(i,j+1),id(i,j),map[i][j]+map[i][j+1]),addedge(id(i,j),id(i,j+1),map[i][j]+map[i][j+1]);
90             }
91         }
92     for(int i=1;i<=m;i++)ans-=map[1][i]+map[n][i];
93     for(int i=1;i<=n;i++)ans-=map[i][1]+map[i][m];
94     ans=ans-maxflow();
95     printf("%d
",ans);
96     return 0;
97 }