记录编号	431034	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HNOI 2013]切糕	最终得分	100
用户昵称	Hzoi_Maple	是否通过	通过
代码语言	C++	运行时间	0.358 s
提交时间	2017-07-31 07:55:11	内存使用	10.87 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define inf 500000
const int T=64001;
const int S=0;
int n,m,num;
int adj[100000];
struct flow{
	int s,t,w,next;	
}k[1000000];
int read(){
	int sum=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
	return sum;
}
void init(int s,int t,int w){
	k[num].s=s;k[num].t=t;k[num].w=w;
	k[num].next=adj[s];adj[s]=num++;
}
int p,f,r,d,cnt,sum;
int w[41][41][41],id[41][41][41];
int dp[64002];
bool bfs(){
	memset(dp,0,sizeof(dp));
	queue<int>q;dp[S]=1;q.push(S);
	while(!q.empty()){
		int o=q.front();q.pop();
		for(int i=adj[o];i!=-1;i=k[i].next){
			if(!k[i].w||dp[k[i].t]) continue;
			dp[k[i].t]=dp[o]+1;
			if(k[i].t==T) return true;
			q.push(k[i].t);
		}	
	}
	return false;
}
int dfs(int o,int fw){
	if(o==T) return fw;
	int tmp=fw,s;
	for(int i=adj[o];i!=-1;i=k[i].next){
		if(!k[i].w||!tmp||dp[k[i].t]!=dp[o]+1) continue;
		s=dfs(k[i].t,min(tmp,k[i].w));
		if(!s){
			dp[k[i].t]=0;continue;
		}
		k[i].w-=s;k[i^1].w+=s;tmp-=s;
	}
	return fw-tmp;
}
int main(){
	freopen("nutcake.in","r",stdin);
	freopen("nutcake.out","w",stdout);
	memset(adj,-1,sizeof(adj));
	p=read();f=read();r=read();
	d=read();
	for(int i=1;i<=r;++i){
		for(int j=1;j<=p;++j)
			for(int u=1;u<=f;++u){
				w[i][j][u]=read();sum+=w[i][j][u];
				id[i][j][u]=++cnt;
				init(id[i-1][j][u],id[i][j][u],w[i][j][u]);
				init(id[i][j][u],id[i-1][j][u],0);
				if(i==r)
					init(id[i][j][u],T,inf),init(T,id[i][j][u],0);
				if(i>d){
					if(j<p)
						init(id[i][j][u],id[i-d][j+1][u],inf),init(id[i-d][j+1][u],id[i][j][u],0);
					if(j>1)
						init(id[i][j][u],id[i-d][j-1][u],inf),init(id[i-d][j-1][u],id[i][j][u],0);
					if(u<f)
						init(id[i][j][u],id[i-d][j][u+1],inf),init(id[i-d][j][u+1],id[i][j][u],0);
					if(u>1)
						init(id[i][j][u],id[i-d][j][u-1],inf),init(id[i-d][j][u-1],id[i][j][u],0);			
				}
			}
	}
	int ans=0;
	while(bfs())
		ans+=dfs(S,inf);
	printf("%d\n",ans);
	// while(1);
	return 0;
}