bzoj3144【HNOI2013】切糕代碼分享

bzoj3144【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

Sample Output

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