3144: [Hnoi2013]切糕

3144: [Hnoi2013]切糕

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 1526  Solved: 827
[Submit][Status][Discuss]

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<cstdio>

#include<cstring>

#include<queue>

using namespace std;

int read(){

    register int x=;bool f=;

    register char ch=getchar();

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

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

    return f?x:-x;

}

const int N=;

const int M=N*N*N;

const int inf=2e9;

int n,m,S,T,head[M],dis[M],q[M*];

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*];int tot=;

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=;e[tot].next=head[y];head[y]=tot;

}

bool bfs(){

    for(int i=S;i<=T;i++) dis[i]=inf;

    int h=,t=;q[t]=S;dis[S]=;

    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]+){

                dis[v]=dis[x]+;

                if(v==T) return ;

                q[++t]=v;

            }

        }

    }

    return dis[T]<inf;

}

int dfs(int x,int f){

    if(x==T) return f;

    int used=,t;

    for(int i=head[x];i;i=e[i].next){

        int v=e[i].v;

        if(e[i].cap&&dis[v]==dis[x]+){

            t=dfs(v,min(f,e[i].cap));

            e[i].cap-=t;e[i^].cap+=t;

            used+=t;f-=t;

            if(!f) return used;

        }

    }

    if(!used) dis[x]=;

    return used;

}

int dinic(){

    int res=;

    while(bfs()) res+=dfs(S,inf);

    return res;

}

int main(){

    scanf("%d%d%d%d",&P,&Q,&R,&D);

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

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

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

                scanf("%d",&mp[i][j][k]);

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

            }

        }

    }

    S=,T=cnt+;

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

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

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

                if(i==)

                    add(S,id[i][j][k],mp[i][j][k]);

                else

                    add(id[i-][j][k],id[i][j][k],mp[i][j][k]);

                if(i==R)

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

                if(i>D){

                    if(j!=) add(id[i][j][k],id[i-D][j-][k],inf);

                    if(j!=P) add(id[i][j][k],id[i-D][j+][k],inf);

                    if(k!=) add(id[i][j][k],id[i-D][j][k-],inf);

                    if(k!=Q) add(id[i][j][k],id[i-D][j][k+],inf);

                }

            }

        }

    }

    printf("%d",dinic());

    return ;

}