BZOJ3144 切糕

http://www.lydsy.com/JudgeOnline/problem.php?id=3144

思路:如果没有D的限制，那一个竖轴都是一个最小割，每个点向更高的点引一条流量为自己权值的边，那考虑D的情况，就表明在割i高度这条边的时候，不能割它相邻的i-d以下的任何边，因此，我们引一条边从i高度到相邻的i-d高度，流量为inf，这样就能维护D这个条件了

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<cstring>

 #include<iostream>

 #define inf 0x7fffffff

 int d[][];

 int sz,id[][][],S,T,nodes,P,Q,R,D;

 int tot,go[],next[],first[],flow[];

 int op[],dis[],cnt[],v[][][];

 int read(){

     int t=,f=;char ch=getchar();

     while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}

     while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}

     return t*f;

 }

 void insert(int x,int y,int z){

     tot++;

     go[tot]=y;

     next[tot]=first[x];

     first[x]=tot;

     flow[tot]=z;

 }

 void add(int x,int y,int z){

     insert(x,y,z);op[tot]=tot+;

     insert(y,x,);op[tot]=tot-;

 }

 int dfs(int x,int f){

     if (x==T) return f;

     int mn=nodes,sum=;

     for (int i=first[x];i;i=next[i]){

         int pur=go[i];

         if (flow[i]&&dis[pur]+==dis[x]){

             int F=std::min(f-sum,flow[i]);

             int save=dfs(pur,F);

             flow[i]-=save;

             flow[op[i]]+=save;

             sum+=save;

             if (sum==f||dis[S]>=nodes) return sum;

         }

         if (flow[i]) mn=std::min(mn,dis[pur]);

     }

     if (sum==){

         cnt[dis[x]]--;

         if (cnt[dis[x]]==) dis[S]=nodes;

         else {

             dis[x]=mn+;

             cnt[dis[x]]++;

         }

     }

     return sum;

 }

 int main(){

     P=read();Q=read();R=read();

     D=read();

     for (int i=;i<=R+;i++)

      for (int j=;j<=P;j++)

       for (int k=;k<=Q;k++)

        id[i][j][k]=++sz;

     S=;T=sz+;nodes=T+;

     for (int i=;i<=R;i++)

      for (int j=;j<=P;j++)

       for (int k=;k<=Q;k++)

        v[i][j][k]=read();

     for (int j=;j<=P;j++)

      for (int k=;k<=Q;k++)

       add(S,id[][j][k],inf);

     for (int j=;j<=P;j++)

      for (int k=;k<=Q;k++)

       add(id[R+][j][k],T,inf);

     for (int i=;i<=R;i++)

      for (int j=;j<=P;j++)

       for (int k=;k<=Q;k++)

        add(id[i][j][k],id[i+][j][k],v[i][j][k]);

     d[][]=d[][]=;d[][]=d[][]=-;

     for (int i=;i<=R;i++)

      if (i>D)

      for (int j=;j<=P;j++)

       for (int k=;k<=Q;k++)

         for (int l=;l<=;l++){

             int dx=j+d[l][],dy=k+d[l][];

             if (dx<||dx>P||dy<||dy>Q) continue;

             add(id[i][j][k],id[i-D][dx][dy],inf);

         }

     int ans=;

     while (dis[S]<nodes) ans+=dfs(S,inf);

     printf("%d\n",ans);

     return ;

 }