圈地计划
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）；
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
观察题目，基本与happiness相同，所以基本也就是二分图的最小割，唯一有差别的是happiness中是属于相同的得到喜悦值，而这个是属于不同集合得到喜悦值。
这一点很难，这一点很难。
最先我想的是把中间的权令为-(w1+w2)，但很明显网络流跑不起负的（可见我网络流多差，这个都不知道），然后怎么办呢？很难办。
既然我们不能用负边连体现这个关系。考虑happiness，A与B点同属于一个集合就得到这个喜悦值，注意到这里指的是属于S集，T集，那么一个精妙的变换方案出现了，我们先黑白染色，对于每个黑点A，S->A:W商业，A->T:W工业，
对于每个白点B，S->B:W工业，B->T:W商业，对于每对有关系的两点A，B，A<-->B:w1+w2。
一切问题就迎刃而解了，真是一种精妙的办法啊。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <ctime>
#include <cmath>
using namespace std;
int s,t;
int n,m;
int sum=0;
int C[200][200];
int tot=1;
int fir[200000],en[200000],nex[200000],f[200000];
void ins(int a,int b,int c,int d){
nex[++tot]=fir[a];
fir[a]=tot;
en[tot]=b;
f[tot]=c; nex[++tot]=fir[b];
fir[b]=tot;
en[tot]=a;
f[tot]=d;
}
int flow;
int d[200000],now[200000],num[200000],pre[200000],his[200000];
void sap(){
flow=0;
for (int i=0;i<=t;i++){
now[i]=fir[i];
d[i]=num[i]=0;
}
num[0]=t;
int aug=0x7fffffff;
bool flag;
int i=s;
while (d[s]<t){
his[i]=aug;
flag=false;
for (int k=now[i];k;k=nex[k])
if (f[k]>0&&d[i]==d[en[k]]+1){
aug=min(aug,f[k]);
flag=true;
now[i]=k;
pre[en[k]]=i;
i=en[k];
if (i==t){
flow+=aug;
while (i!=s){
i=pre[i];
f[now[i]]-=aug;
f[now[i]^1]+=aug;
}
aug=0x7fffffff;
}
break;
}
if (flag) continue;
int k1=0,minn=t;
for (int k=fir[i];k;k=nex[k])
if (f[k]>0&&minn>d[en[k]]){
k1=k;
minn=d[en[k]];
}
now[i]=k1;
if (!--num[d[i]]) return;
d[i]=minn+1;
num[d[i]]++; if (i!=s){
i=pre[i];
aug=his[i];
}
}
}
int main(){
// freopen("2132.in","r",stdin);
// freopen("2132.out","w",stdout);
scanf("%d%d",&n,&m);
s=n*m+1;t=n*m+2;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++){
int delta;
scanf("%d",&delta);
if ((i+j)%2==0) ins(s,(i-1)*m+j,delta,0);
if ((i+j)%2==1) ins((i-1)*m+j,t,delta,0);
sum+=delta;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++){
int delta;
scanf("%d",&delta);
if ((i+j)%2==1) ins(s,(i-1)*m+j,delta,0);
if ((i+j)%2==0) ins((i-1)*m+j,t,delta,0);
sum+=delta;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++){
scanf("%d",&C[i][j]);
}
for (int i=1;i<=n;i++)
for (int j=1;j<=m-1;j++){
ins((i-1)*m+j,(i-1)*m+j+1,C[i][j]+C[i][j+1],C[i][j]+C[i][j+1]);
sum+=C[i][j]+C[i][j+1];
}
for (int i=1;i<=n-1;i++)
for (int j=1;j<=m;j++){
ins((i-1)*m+j,i*m+j,C[i][j]+C[i+1][j],C[i][j]+C[i+1][j]);
sum+=C[i][j]+C[i+1][j];
}
sap(); printf("%d",sum-flow); return 0;
}