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

bzoj2127 happiness

編輯:C++入門知識

bzoj2127 happiness


 

2127: happiness

Time Limit: 51 Sec Memory Limit: 259 MB
Submit: 1198 Solved: 574
[Submit][Status][Discuss]

Description

高一一班的座位表是個n*m的矩陣,經過一個學期的相處,每個同學和前後左右相鄰的同學互相成為了好朋友。這學期要分文理科了,每個同學對於選擇文科與理科有著自己的喜悅值,而一對好朋友如果能同時選文科或者理科,那麼他們又將收獲一些喜悅值。作為計算機競賽教練的scp大老板,想知道如何分配可以使得全班的喜悅值總和最大。

Input

第一行兩個正整數n,m。接下來是六個矩陣第一個矩陣為n行m列 此矩陣的第i行第j列的數字表示座位在第i行第j列的同學選擇文科獲得的喜悅值。第二個矩陣為n行m列 此矩陣的第i行第j列的數字表示座位在第i行第j列的同學選擇理科獲得的喜悅值。第三個矩陣為n-1行m列 此矩陣的第i行第j列的數字表示座位在第i行第j列的同學與第i+1行第j列的同學同時選擇文科獲得的額外喜悅值。第四個矩陣為n-1行m列 此矩陣的第i行第j列的數字表示座位在第i行第j列的同學與第i+1行第j列的同學同時選擇理科獲得的額外喜悅值。第五個矩陣為n行m-1列 此矩陣的第i行第j列的數字表示座位在第i行第j列的同學與第i行第j+1列的同學同時選擇文科獲得的額外喜悅值。第六個矩陣為n行m-1列 此矩陣的第i行第j列的數字表示座位在第i行第j列的同學與第i行第j+1列的同學同時選擇理科獲得的額外喜悅值。

Output

輸出一個整數,表示喜悅值總和的最大值

Sample Input

1 2
1 1
100 110
1
1000

Sample Output

1210
【樣例說明】
兩人都選理,則獲得100+110+1000的喜悅值。
【數據規模】
對於100%以內的數據,n,m<=100 所有喜悅值均為小於等於5000的非負整數

HINT

Source

“There is no Y in happiness.It’s an I.” 將這句電影台詞獻給同我一樣、奔跑在happiness之路上的追夢人。

好了,言歸正傳,這是一道思路很不錯的最小割題。

這道題我們的思想依然為先將所有喜悅值加起來,再從中減去最小割,即為答案。

我們定義s割為文科,t割為理科。

對於每個人i,連邊(s,i,c文[i])) (i,t,c理[i])。這裡是很好理解的,如果一個人不學文科或理科,自然會失去相應的喜悅值。

對於每兩個相鄰的人i和j,連邊(s,i,c文[i][j]/2) (s,j,c文[i][j]/2) (i,t,c理[i][j]/2) (j,t,c理[i][j]/2) (i,j,(c文[i][j]+c理[i][j])/2) (j,i,(c文[i][j]+c理[i][j])/2)。至於為什麼這樣加邊呢?大家畫個圖就懂了。注意要分都學文、都學理、一文一理三種情況。

這道題還有一個優化的技巧,對於起點和終點相同的邊,我們可以將幾次的權值求和,一次插入。這樣可以減少邊的數量,自然就可以降低時間復雜度。

#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];
int a[105][105],b[105][105],c[105][105];
int s,t,n,m,x,ans=0,tot=0,cnt=1;
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)
{
	int tmp,sum=0;
	if (x==t) return f;
	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)
	{
		a[i][j]=read();
		tot+=a[i][j];
		a[i][j]<<=1;
	}
	F(i,1,n) F(j,1,m)
	{
		b[i][j]=read();
		tot+=b[i][j];
		b[i][j]<<=1;
	}
	F(i,1,n-1) F(j,1,m)
	{
		x=read();
		tot+=x;
		a[i][j]+=x;
		a[i+1][j]+=x;
		c[i][j]+=x;
	}
	F(i,1,n-1) F(j,1,m)
	{
		x=read();
		tot+=x;
		b[i][j]+=x;
		b[i+1][j]+=x;
		c[i][j]+=x;
	}
	F(i,1,n-1) F(j,1,m) add_edge(f(i,j),f(i+1,j),c[i][j],c[i][j]);
	memset(c,0,sizeof(c));
	F(i,1,n) F(j,1,m-1)
	{
		x=read();
		tot+=x;
		a[i][j]+=x;
		a[i][j+1]+=x;
		c[i][j]+=x;
	}
	F(i,1,n) F(j,1,m-1)
	{
		x=read();
		tot+=x;
		b[i][j]+=x;
		b[i][j+1]+=x;
		c[i][j]+=x;
	}
	F(i,1,n) F(j,1,m-1) add_edge(f(i,j),f(i,j+1),c[i][j],c[i][j]);
	F(i,1,n) F(j,1,m)
	{
		add_edge(s,f(i,j),a[i][j],0);
		add_edge(f(i,j),t,b[i][j],0);
	}
	dinic();
	tot-=(ans>>1);
	printf("%d\n",tot);
}

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