程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> bzoj2132 圈地計劃

bzoj2132 圈地計劃

編輯:關於C++

 

2132: 圈地計劃

Time Limit: 2 Sec Memory Limit: 256 MB
Submit: 661 Solved: 295
[Submit][Status][Discuss]

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

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);
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved