记录编号	367057	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HNOI 2013]切糕	最终得分	100
用户昵称	_Itachi	是否通过	通过
代码语言	C++	运行时间	0.457 s
提交时间	2017-01-27 18:31:23	内存使用	11.54 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=64005,maxm=maxn*5,INF=0x3f3f3f3f;
struct Rabit_tree{int to,next,c,f;}e[maxm<<1];
int l,m,n,D,N=0,S,T,pos[41][41][41],head[maxn],len=1;
int fx[4]={0,0,1,-1},fy[4]={1,-1,0,0};
void Rabit_Set(int prt,int son,int cap){
	e[++len].to=son,e[len].next=head[prt],head[prt]=len,
	e[len].c=cap,e[len].f=0;	
}
void Rabit_set(int prt,int son,int cap){
	Rabit_Set(prt,son,cap),Rabit_Set(son,prt,0);	
}
#define to e[i].to
int cur[maxn],Dp[maxn],vis[maxn],tim=0,q[maxn];
bool Rabit_run(){
	int s,t,rt,i;q[s=t=1]=S,vis[S]=++tim,Dp[S]=0;
	while(s<=t){
		rt=q[s++];
		for(i=head[rt];i;i=e[i].next)
			if(e[i].c>e[i].f&&vis[to]^tim)
				q[++t]=to,vis[to]=tim,Dp[to]=Dp[rt]+1;
	}
	return vis[T]==tim;
}
int Rabit_run(int rt,int v){
	if(rt==T||!v)return v;
	int flow=0,tmp;
	for(int &i=cur[rt];i;i=e[i].next)
		if(Dp[to]==Dp[rt]+1){
			tmp=Rabit_run(to,min(v,e[i].c-e[i].f));
			if(tmp){
				e[i].f+=tmp,e[i^1].f-=tmp,v-=tmp,flow+=tmp;
				if(!v)break;	
			}
		}
	return flow;
}
int Rabit_dinic(){
	int flow=0,i;
	while(Rabit_run()){
		for(i=1;i<=T;i++)cur[i]=head[i];
		flow+=Rabit_run(S,INF);
	}
	return flow;
}
void Rabit_in(){
	scanf("%d%d%d%d",&l,&m,&n,&D);int i,j,k,p,x,y,z;
	for(i=1;i<=l;i++)
	for(j=1;j<=m;j++)
	for(k=1;k<=n;k++)
		pos[i][j][k]=++N;
	S=N+1,T=N+2;
	for(k=1;k<=n;k++)
	for(i=1;i<=l;i++)
	for(j=1;j<=m;j++){
		scanf("%d",&z);
		if(k==1)Rabit_set(S,pos[i][j][k],z),Rabit_set(pos[i][j][n],T,INF);
		else Rabit_set(pos[i][j][k-1],pos[i][j][k],z);
		if(k>D){
			for(p=0;p<4;p++){
				x=fx[p]+i,y=fy[p]+j;
				if(pos[x][y][k-D])Rabit_set(pos[i][j][k],pos[x][y][k-D],INF);	
			}
		}
	}
}
int main(){
	freopen("nutcake.in","r",stdin);freopen("nutcake.out","w",stdout);
	Rabit_in();
	printf("%d\n",Rabit_dinic());
}