题目概述

有一块 $X\times Y\times Z$ 的切糕，每个点 $(x,y,z)$ 都有不和谐值 $v(x,y,z)$ 。现在要切这块切糕，为每个直线 $(x,y)$ 选出一个点 $z$ ，一种切法的不和谐值为选出点的不和谐值之和，为了平整还需要满足两条相邻的直线选出的点距离不超过 $D$ 。求最小不和谐值。

解题报告

声名远扬(?)的切糕模型，如果没有距离限制，我们可以把每个 $(x,y)$ 都从 $S$ 到 $T$ 串起来，像这样：

S -> 1 -> 2 -> 3 -> ... -> T

将每条边的容量设置为不和谐值，然后求最小割就是最优解。

但是有限制，我们可以用容量为INF的边实现“屏蔽”效果，对于网络中的点 $(x,y,z)$ ，在 $(x,y,z-1)\to (x',y',z-1-D)$ 和 $(x',y',z+D)\to (x,y,z)$ 之间（ $(x,y)$ 与 $(x',y')$ 相邻）连容量为INF的边，这样就会形成一个 $S\to (x,y,z-1)\to (x',y',z-D)\to (x',y',z+D)\to (x,y,z)\to T$ 的“通路”，从而阻止其他边被选。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=40,maxt=maxn*maxn*maxn,maxe=(maxt+(maxt<<3))<<1;
const int fl[4][2]={{-1,0},{0,-1},{0,1},{1,0}},INF=2e9;

int X,Y,Z,D,n,ans;pair<int,int> e[maxe+5];
int E,lnk[maxt+5],son[maxe+5],nxt[maxe+5];
int que[maxt+5],dis[maxt+5],ti,vis[maxt+5],cur[maxt+5];

inline int ID(int x,int y,int z) {if (!z) return 0;return z<Z?(x-1)*Y*Z+(y-1)*Z+z:n+1;}
inline void Add(int x,int y,int z){
    son[E]=y;e[E]=mp(0,z);nxt[E]=lnk[x];lnk[x]=E++;
    son[E]=x;e[E]=mp(0,0);nxt[E]=lnk[y];lnk[y]=E++;
}
inline bool Bfs(int s,int t){
    int Head=0,Tail=0;que[++Tail]=s;vis[s]=++ti;dis[s]=0;
    while (Head!=Tail)
        for (int x=que[++Head],j=lnk[x],u;~j;j=nxt[j])
            if (vis[u=son[j]]<ti&&e[j].fr<e[j].sc) que[++Tail]=u,vis[u]=ti,dis[u]=dis[x]+1;
        return vis[t]==ti;        
}
int Dfs(int x,int t,int MIN=INF){
    if (x==t||!MIN) return MIN;int f=0,now;
    for (int &j=cur[x];~j;j=nxt[j])
        if (dis[x]+1==dis[son[j]]&&(now=Dfs(son[j],t,min(MIN,e[j].sc-e[j].fr)))){
            e[j].fr+=now;e[j^1].fr-=now;f+=now;
            if (!(MIN-=now)) break;
        }
    return f;
}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d%d%d%d",&X,&Y,&Z,&D);n=X*Y*Z;E=0;memset(lnk,255,sizeof(lnk));
    for (int z=1;z<=Z;z++)
        for (int x=1;x<=X;x++)
            for (int y=1,val;y<=Y;y++)
                scanf("%d",&val),Add(ID(x,y,z-1),ID(x,y,z),val);
    for (int i=1;i<=X;i++)
        for (int j=1;j<=Y;j++)
            for (int f=0;f<4;f++){
                int x=i+fl[f][0],y=j+fl[f][1];
                if (x<1||x>X||y<1||y>Y) continue;
                for (int k=1;k<=Z;k++){
                    if (k>D+1) Add(ID(i,j,k-1),ID(x,y,k-1-D),INF);
                    if (k+D<Z) Add(ID(i,j,k+D),ID(x,y,k),INF);
                }
            }
    while (Bfs(0,n+1)) memcpy(cur,lnk,sizeof(lnk)),ans+=Dfs(0,n+1);
    return printf("%d\n",ans),0;
}