bzoj2132 圈地計劃

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

Sample Output

HINT

數據已加強，並重測--2015.5.15

Source

和bzoj1976能量魔方類似，不過這道題是二維的。

我們先將所有點黑白染色。對於黑點i，從s到i連權值為a[i]的邊，從i到t連權值為b[i]的邊；對於白點i，從s到i連權值為b[i]的邊，從i到t連權值為a[i]的邊。對於相鄰的兩個點i和j，從i到j、從j到i分別連權值為c[i]+c[j]的邊。

最後跑一次最小割，從最初的總收益中減去最小割。

#include
#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define pa pair
#define maxn 10100
#define maxm 100100
#define inf 1000000000
#define f(x,y) (x-1)*m+y
using namespace std;
struct edge_type
{
	int next,to,v;
}e[maxm];
int head[maxn],cur[maxn],dis[maxn],a[105][105];
int n,m,s,t,x,cnt=1,ans=0,tot=0;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void add_edge(int x,int y,int v1,int v2)
{
	e[++cnt]=(edge_type){head[x],y,v1};head[x]=cnt;
	e[++cnt]=(edge_type){head[y],x,v2};head[y]=cnt;
}
inline bool bfs()
{
	queueq;
	memset(dis,-1,sizeof(dis));
	dis[s]=0;q.push(s);
	while (!q.empty())
	{
		int tmp=q.front();q.pop();
		if (tmp==t) return true;
		for(int i=head[tmp];i;i=e[i].next) if (e[i].v&&dis[e[i].to]==-1)
		{
			dis[e[i].to]=dis[tmp]+1;
			q.push(e[i].to);
		}
	}
	return false;
}
inline int dfs(int x,int f)
{
	if (x==t) return f;
	int tmp,sum=0;
	for(int &i=cur[x];i;i=e[i].next)
	{
		int y=e[i].to;
		if (e[i].v&&dis[y]==dis[x]+1)
		{
			tmp=dfs(y,min(f-sum,e[i].v));
			e[i].v-=tmp;e[i^1].v+=tmp;sum+=tmp;
			if (sum==f) return sum;
		}
	}
	if (!sum) dis[x]=-1;
	return sum;
}
inline void dinic()
{
	while (bfs())
	{
		F(i,1,t) cur[i]=head[i];
		ans+=dfs(s,inf);
	}
}
int main()
{
	n=read();m=read();
	s=n*m+1;t=s+1;
	F(i,1,n) F(j,1,m)
	{
		x=read();
		tot+=x;
		if ((i+j)&1) add_edge(s,f(i,j),x,0);
		else add_edge(f(i,j),t,x,0);
	}
	F(i,1,n) F(j,1,m)
	{
		x=read();
		tot+=x;
		if ((i+j)&1) add_edge(f(i,j),t,x,0);
		else add_edge(s,f(i,j),x,0);
	}
	F(i,1,n) F(j,1,m) a[i][j]=read();
	F(i,1,n) F(j,1,m-1)
	{
		int tmp=a[i][j]+a[i][j+1];
		tot+=tmp;
		add_edge(f(i,j),f(i,j+1),tmp,tmp);
	}
	F(i,1,n-1) F(j,1,m)
	{
		int tmp=a[i][j]+a[i+1][j];
		tot+=tmp;
		add_edge(f(i,j),f(i+1,j),tmp,tmp);
	}
	dinic();
	printf("%d\n",tot-ans);
}