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

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#define inf 10000000
using namespace std;
struct bian
{
  int qi,zhong,w,next;
};
bian c[1000000];
int n,m,r,d,jishu=0,hd,tl,ji=0,ying,xuan;
int v[50][50][50],num[50][50][50],head[100000],dep[100000],q[100000];
void add(int x,int y,int z)
{
  c[jishu].qi=x;
  c[jishu].zhong=y;
  c[jishu].w=z;
  c[jishu].next=head[x];
  head[x]=jishu++;
}
bool bfs()
{
  memset(dep,0,sizeof(dep));
  hd=tl=0;
  q[++tl]=0;
  dep[0]=1;
  while(hd<tl)
  {
    int op=q[++hd];
    for(int i=head[op];i!=-1;i=c[i].next)
    {
      if(c[i].w&&(!dep[c[i].zhong]))
      {
        dep[c[i].zhong]=dep[op]+1;
        q[++tl]=c[i].zhong;
        if(c[i].zhong==ying)
          return 1;
      }
    }
  }
  return 0;
}
int dfs(int op,int fw)
{
  if(op==ying)  return fw;
  int tmp=fw,k;
  for(int i=head[op];i!=-1;i=c[i].next)
  {
    if(c[i].w&&tmp&&dep[c[i].zhong]==dep[op]+1)
    {
      k=dfs(c[i].zhong,min(c[i].w,tmp));
      if(!k)
      {
        dep[c[i].zhong]=0;
        continue;
      }
      c[i].w-=k;
      c[i^1].w+=k;
      tmp-=k;
    }
  }
  return fw-tmp;
}
int main()
{
  freopen("nutcake.in","r",stdin);
  freopen("nutcake.out","w",stdout);
	memset(head,-1,sizeof(head));
  scanf("%d%d%d%d",&n,&m,&r,&d);
  xuan=0;ying=n*m*(r+1)+1;
  for(int i=1;i<=r;++i)
    for(int j=1;j<=n;++j)
      for(int k=1;k<=m;++k)
      {
        scanf("%d",&v[i][j][k]);
        num[i][j][k]=++ji;
      }
  for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)
      num[r+1][i][j]=++ji;
  for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)
    {
      add(xuan,num[1][i][j],inf);
      add(num[1][i][j],xuan,0);
    }
  for(int i=1;i<=n;++i)
    for(int j=1;j<=m;++j)
    {
		  add(num[r+1][i][j],ying,inf);
      add(ying,num[r+1][i][j],0);
    }
  for(int i=1;i<=r;++i)
    for(int j=1;j<=n;++j)
      for(int k=1;k<=m;++k)
      {
        add(num[i][j][k],num[i+1][j][k],v[i][j][k]);
        add(num[i+1][j][k],num[i][j][k],0);
      }
  for(int i=r+1;i>=d+1;--i)
    for(int j=1;j<=n;++j)
      for(int k=1;k<=m;++k)
      {
        add(num[i][j][k],num[i-d][j+1][k],inf);
        add(num[i-d][j+1][k],num[i][j][k],0);
        add(num[i][j][k],num[i-d][j-1][k],inf);
        add(num[i-d][j-1][k],num[i][j][k],0);
        add(num[i][j][k],num[i-d][j][k+1],inf);
        add(num[i-d][j][k+1],num[i][j][k],0);
        add(num[i][j][k],num[i-d][j][k-1],inf);
        add(num[i-d][j][k-1],num[i][j][k],0);
      }
  int shu=0;
  while(bfs())
    shu+=dfs(0,inf);
  printf("%d",shu);
  return 0;
}