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

bzoj3144【HNOI2013】切糕代碼分享

編輯:C++入門知識

bzoj3144【HNOI2013】切糕代碼分享


 

3144: [Hnoi2013]切糕

Description

\

 

Input

第一行是三個正整數P,Q,R,表示切糕的長P、 寬Q、高R。第二行有一個非負整數D,表示光滑性要求。接下來是R個P行Q列的矩陣,第z個 矩陣的第x行第y列是v(x,y,z) (1≤x≤P, 1≤y≤Q, 1≤z≤R)。
100%的數據滿足P,Q,R≤40,0≤D≤R,且給出的所有的不和諧值不超過1000。

 

Output

僅包含一個整數,表示在合法基礎上最小的總不和諧值。

 

Sample Input

2 2 2
1
6 1
6 1
2 6
2 6
 

Sample Output

6  

HINT

 

最佳切面的f為f(1,1)=f(2,1)=2,f(1,2)=f(2,2)=1

 

 

 

 

 

很經典的最小割問題。

這道題的關鍵是如何限制相鄰兩點的差不超過d。首先我們按高度分層,每層的點向下一層相同位置的點連邊,邊權就是對應的層數,所以最後我們會多設一層。這樣如果我們刪去某條邊就意味著選擇了下面這個點。然後對於d的限制,我們從k層的點到k-d層的相鄰節點連正無窮的邊,因為選擇了這條邊再選擇上面的邊就不能構成最小割了,所以只能選擇下面的邊。而如果我們互相都連邊,就限制了彼此的差不超過d。最後從s到第1層的點、從第n+1層的點到t分別連正無窮的邊,顯然這些邊也是不能成為割邊的。

這樣構圖後,最後跑一遍最小割就可以了。


 

 

 

#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 maxn 70000
#define maxm 2000000
#define inf 1000000000
using namespace std;
int n,m,h,d,s,t,ans,cnt=1;
int f[45][45][45],dis[maxn],cur[maxn],head[maxn];
int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
struct edge_type{int next,to,v;}e[maxm];
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 v)
{
	e[++cnt]=(edge_type){head[x],y,v};head[x]=cnt;
	e[++cnt]=(edge_type){head[y],x,0};head[y]=cnt;
}
inline bool bfs()
{
	queueq;
	while (!q.empty()) q.pop();
	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,s,t) cur[i]=head[i];
		ans+=dfs(s,inf);
	}
}
inline int g(int x,int y,int z)
{
	return (z-1)*n*m+(x-1)*m+y;
}
int main()
{
	n=read();m=read();h=read();d=read();
	s=0;t=n*m*(h+1)+1;
	F(k,1,h) F(i,1,n) F(j,1,m) f[i][j][k]=read();
	F(i,1,n) F(j,1,m)
	{
		add_edge(s,g(i,j,1),inf);add_edge(g(i,j,h+1),t,inf);
		F(k,1,h)
		{
			add_edge(g(i,j,k),g(i,j,k+1),f[i][j][k]);
			if (k>d) F(l,0,3)
			{
				int nx=i+dx[l],ny=j+dy[l];
				if (nx<1||nx>n||ny<1||ny>m) continue;
				add_edge(g(i,j,k),g(nx,ny,k-d),inf);
			}
		}
	}
	dinic();
	printf("%d\n",ans);
	return 0;
}


 

 

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