3144: [Hnoi2013]切糕

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 1526  Solved: 827

[][][]

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

 

经典最小割模型

题面简化为，一个矩阵，每个格子分配一个数，不同的数字，代价不同，要求相邻格子数字差小等于d

求最小代价

每个格子拆出40个点

连同S与T用40种代价串起来

即 p(x,y,z)->p(x,y,z+1)边权f(x,y,z+1)

然后 p(x,y,z)->p(x’,y’,z-d)边权inf (x,y)与(x’,y’)相邻

把边画出来正确性很显然

 

#include
     
      #include
      
       #include
       
        using namespace std;int read(){    register int x=0;bool f=1;    register char ch=getchar();    while(ch<'0'||ch>'9'){
   if(ch=='-')f=0;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return f?x:-x;}const int N=50;const int M=N*N*N;const int inf=2e9;int n,m,S,T,head[M],dis[M],q[M*10];bool vis[M];int P,Q,R,D,mp[N][N][N],id[N][N][N],cnt;struct node{    int v,next,cap;}e[M*10];int tot=1;void add(int x,int y,int z){    e[++tot].v=y;e[tot].cap=z;e[tot].next=head[x];head[x]=tot;    e[++tot].v=x;e[tot].cap=0;e[tot].next=head[y];head[y]=tot;}bool bfs(){    for(int i=S;i<=T;i++) dis[i]=inf;    int h=0,t=1;q[t]=S;dis[S]=0;    while(h!=t){        int x=q[++h];        for(int i=head[x];i;i=e[i].next){            int v=e[i].v;            if(e[i].cap&&dis[v]>dis[x]+1){                dis[v]=dis[x]+1;                if(v==T) return 1;                q[++t]=v;            }        }    }    return dis[T]
        
         D){                    if(j!=1) add(id[i][j][k],id[i-D][j-1][k],inf);                    if(j!=P) add(id[i][j][k],id[i-D][j+1][k],inf);                    if(k!=1) add(id[i][j][k],id[i-D][j][k-1],inf);                    if(k!=Q) add(id[i][j][k],id[i-D][j][k+1],inf);                }            }        }    }    printf("%d",dinic());    return 0;}