Bzoj3144 [Hnoi2013]切糕

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1494  Solved: 818

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

2 2 2
1
6 1
6 1
2 6
2 6

Sample Output

6

HINT

最佳切面的f为f(1,1)=f(2,1)=2,f(1,2)=f(2,2)=1

Source

网络流 最小割

从底层到顶层连边，每条(x,y)纵轴成为一条链，其上边的容量等于割掉的花费，S连底层，顶层连T。

利用INF边限制D，求最小割。

http://blog.csdn.net/thy_asdf/article/details/50428973

↑这里讲得挺详细

 /*by SilverN*/

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<queue>

 using namespace std;

 const int INF=1e9;

 const int mx[]={,,,-,};

 const int my[]={,,,,-};

 const int mxn=;

 int read(){

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

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

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

     return x*f;

 }

 struct edge{

     int v,nxt,f;

 }e[mxn<<];

 int hd[mxn],mct=;

 void add_edge(int u,int v,int c){

     e[++mct].v=v;e[mct].f=c;e[mct].nxt=hd[u];hd[u]=mct;return;

 }

 void insert(int u,int v,int c){

     add_edge(u,v,c);add_edge(v,u,);return;

 }

 int n,m,S,T;

 int P,Q,R;

 int w[][][];

 int d[mxn];

 bool BFS(){

     memset(d,,sizeof d);

     d[S]=;

     queue<int>q;

     q.push(S);

     while(!q.empty()){

         int u=q.front();q.pop();

         for(int i=hd[u];i;i=e[i].nxt){

             int v=e[i].v;

             if(!d[v] && e[i].f){

                 d[v]=d[u]+;q.push(v);

             }

         }

     }

     return d[T];

 }

 int DFS(int u,int lim){

     if(u==T)return lim;

     int tmp,f=;

     for(int i=hd[u];i;i=e[i].nxt){

         int v=e[i].v;

         if(d[v]==d[u]+ && e[i].f){

             tmp=DFS(v,min(lim,e[i].f));

             e[i].f-=tmp;

             e[i^].f+=tmp;

             lim-=tmp;

             f+=tmp;

             if(!lim)return f;

         }

     }

     d[u]=;

     return f;

 }

 int Dinic(){

     int res=;

     while(BFS())res+=DFS(S,1e9);

     return res;

 }

 int id[][][];

 void init(){

     int cnt=;

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

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

         for(int z=;z<=R;z++){

             id[x][y][z]=++cnt;

     }

     return;

 }

 int main(){

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

     int i,j,k,D=read();

     init();

     S=;T=P*Q*R+;

     for(i=;i<=R;i++)//z

         for(j=;j<=P;j++)//x

             for(k=;k<=Q;k++){//y

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

     }

     for(i=;i<=P;i++)//x

         for(j=;j<=Q;j++){//y

             for(k=;k<=R;k++){//z

                 insert(id[i][j][k-],id[i][j][k],w[i][j][k]);

                 if(k>D){

                     int nx,ny;

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

                         nx=i+mx[l];

                         ny=j+my[l];

                         if(nx< || nx>P || ny< || ny>Q)continue;

                         insert(id[i][j][k],id[nx][ny][k-D],INF);

                     }

                 }

             }

             insert(id[i][j][R],T,INF);

         }

     int ans=Dinic();

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

     return ;

 }