[HNOI2013]切糕

Time Limit: 10 Sec Memory Limit: 128 MB

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

HINT

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

题解：
http://www.cnblogs.com/Yuzao/p/7367429.html

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cstdlib>
  5 #include<cmath>
  6 #include<algorithm>
  7 #include<queue>
  8 #define inf (2e8)
  9 using namespace std;
 10 int head[70001],size=1,n,m,l,d,map[41][41][41],s=0,t,pos[41][41][41],cnt;
 11 struct node
 12 {
 13     int next,to,cap;
 14 }edge[700001];
 15 void putin(int from,int to,int cap)
 16 {
 17     size++;
 18     edge[size].next=head[from];
 19     edge[size].to=to;
 20     edge[size].cap=cap;
 21     head[from]=size;
 22 }
 23 void in(int from,int to,int cap)
 24 {
 25     putin(from,to,cap);
 26     putin(to,from,0);
 27 }
 28 int gi()
 29 {
 30     int ans=0,f=1;
 31     char i=getchar();
 32     while(i<'0'||i>'9'){if(i=='-')f=-1;i=getchar();}
 33     while(i>='0'&&i<='9'){ans=ans*10+i-'0';i=getchar();}
 34     return ans*f;
 35 }
 36 int dist[70001],numbs[70001],vis[70001];
 37 void bfs(int src,int des)
 38 {
 39     int i;
 40     for(i=0;i<=cnt+1;i++){dist[i]=cnt+2;numbs[i]=0;}
 41     dist[des]=0;
 42     numbs[0]=1;
 43     queue<int>mem;
 44     mem.push(des);
 45     while(!mem.empty())
 46     {
 47         int x=mem.front();mem.pop();
 48         vis[x]=0;
 49         for(i=head[x];i!=-1;i=edge[i].next)
 50         {
 51             int y=edge[i].to;
 52             if(edge[i].cap==0&&dist[y]==cnt+2)
 53             {
 54                 dist[y]=dist[x]+1;
 55                 numbs[dist[y]]++;
 56                 if(!vis[y])
 57                 {
 58                     mem.push(y);
 59                     vis[y]=1;
 60                 }
 61             }
 62         }
 63     }
 64 }
 65 int dfs(int root,int flow,int des)
 66 {
 67     if(root==des)return flow;
 68     int res=0,mindist=cnt+2;
 69     for(int i=head[root];i!=-1;i=edge[i].next)
 70     {
 71         if(edge[i].cap>0)
 72         {
 73             int y=edge[i].to;
 74             if(dist[root]==dist[y]+1)
 75             {
 76                 int tmp=dfs(y,min(flow-res,edge[i].cap),des);
 77                 edge[i].cap-=tmp;
 78                 edge[i^1].cap+=tmp;
 79                 res+=tmp;
 80                 if(dist[0]>=cnt+2)return res;
 81                 if(res==flow)break;
 82             }
 83             mindist=min(mindist,dist[y]+1);
 84         }
 85     }
 86     if(!res)
 87     {
 88         if(!(--numbs[dist[root]]))dist[0]=cnt+2;
 89         ++numbs[dist[root]=mindist];
 90     }
 91     return res;
 92 }
 93 int ISAP(int src,int des)
 94 {
 95     bfs(src,des);
 96     int f=0;
 97     while(dist[src]<cnt+2)
 98         f+=dfs(src,2e8,des);
 99     return f;
100 }
101 int main()
102 {
103     int i,j,k;
104     memset(head,-1,sizeof(head));
105     n=gi();m=gi();l=gi();d=gi();
106     for(i=1;i<=n;i++)
107         for(j=1;j<=m;j++)
108             pos[0][i][j]=++cnt;
109     for(i=1;i<=l;i++)
110         for(j=1;j<=n;j++)
111             for(k=1;k<=m;k++)
112                 map[i][j][k]=gi(),pos[i][j][k]=++cnt;
113     t=cnt+1;
114     for(i=1;i<=n;i++)
115         for(j=1;j<=m;j++)
116             in(s,pos[0][i][j],inf),in(pos[l][i][j],t,inf);
117     for(i=1;i<=l;i++)
118         for(j=1;j<=n;j++)
119             for(k=1;k<=m;k++)
120                 in(pos[i-1][j][k],pos[i][j][k],map[i][j][k]);
121     for(i=d+1;i<=l;i++)
122         for(j=1;j<=n;j++)
123             for(k=1;k<=m;k++)
124             {
125                 if(j>1)in(pos[i][j][k],pos[i-d][j-1][k],inf);
126                 if(j<n)in(pos[i][j][k],pos[i-d][j+1][k],inf);
127                 if(k>1)in(pos[i][j][k],pos[i-d][j][k-1],inf);
128                 if(k<m)in(pos[i][j][k],pos[i-d][j][k+1],inf);
129             }
130     int maxflow=0;
131     maxflow=ISAP(s,t);
132     printf("%d
",maxflow);
133     return 0;
134 }