题解

把切面看成从柱状体中挑选出每根纵轴的一个高度，同时对相邻纵轴施加 “高度差不超过 $D$” 的限制。经典做法是把选取过程转化为一次最小割：对于每根纵轴 $(x,y)$，建出从底到顶共 $R+1$ 个节点，依次用容量为 $v(x,y,z)$ 的边把高度 $z$ 与 $z+1$ 连接起来，再用无穷大容量的边把底部连向源点、顶部连向汇点。这样一来，割掉的第一条垂直边恰好表示切面在该纵轴的高度，且总代价正好是所有被切断的竖向边容量之和。

为了保证相邻纵轴的高度差不超过 $D$，如果在 $(x,y)$ 上选择高度 $h$，那么相邻列 $(x',y')$ 的高度必须属于 $[h-D, h+D]$。在网络中可以通过额外的无穷大边实现：对于每个 $(x,y)$、每个 $z>D$，向四个相邻纵轴的节点 $(x',y',z-D)$ 连一条容量为无穷的边。这样，如果两根纵轴的切点相差超过 $D$，割集就会被迫同时割掉这些无穷大边，从而不可行。

最终在这个图上跑一次 Dinic 求最小割即可。割值就是满足所有约束的切面上不和谐值的最小总和。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'

const int MAXP=59,N=MAXP*MAXP*MAXP*2,M=2e6+9;
const ll INF=1e13;
int p,q,r;
int D;
int v[MAXP][MAXP][MAXP];
int head[N],nxt[M],to[M];
ll w[M];
int s,t;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
ll ans=0;
int d[N];
int cnt=-1;
int now[N];

int chg(int x,int y,int z){
	return x*q*(r+1)+y*(r+1)+z;
}
void add(int u,int v,ll k){
	nxt[++cnt]=head[u];
	head[u]=cnt;
	w[cnt]=k,to[cnt]=v;
	nxt[++cnt]=head[v];
	head[v]=cnt;
	w[cnt]=0,to[cnt]=u;
	return;
}
void print_edge(){
	for(int i=s;i<=t;i++){
		cout<<i<<endl;
		for(int j=head[i];j!=-1;j=nxt[j])
			cout<<to[j]<<" "<<w[j]<<endl;
	}
	return;
}

bool bfs(){
	for(int i=s;i<=t;i++)d[i]=0;
	d[s]=1;
	queue<int> q;
	q.push(s);
	while(!q.empty()){
		int f=q.front();q.pop();
		if(f==t)return 1;
		for(int i=head[f];i!=-1;i=nxt[i]){
			int v=to[i];
			if(d[v]||!w[i])continue;
			d[v]=d[f]+1;
			q.push(v);
		}
	}
	return 0;
}
ll dfs(int u,ll f){
	if(u==t)return f;
	ll sum=0;
	for(int i=now[u];i!=-1;i=nxt[i]){
		int v=to[i];
		if(d[v]!=d[u]+1||!w[i])continue;
		ll tmp=dfs(v,min(w[i],f-sum));
		if(tmp){
			w[i]-=tmp,w[i^1]+=tmp;
			sum+=tmp;
			now[u]=i;
		}
		else d[v]=-1;
	}
	return sum;
}

void Dinic(){
	while(bfs()){
		for(int i=s;i<=t;i++)now[i]=head[i];
		ans+=dfs(s,1e17);
	}
	return;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
	cin>>p>>q>>r;
	cin>>D;
	s=0,t=chg(p,q,r+1)+1;
	for(int i=s;i<=t;i++)head[i]=-1;
	for(int k=1;k<=r;k++)for(int i=1;i<=p;i++)for(int j=1;j<=q;j++)cin>>v[i][j][k];
	for(int x=1;x<=p;x++)
		for(int y=1;y<=q;y++){
			add(s,chg(x,y,1),INF);
			add(chg(x,y,r+1),t,INF);
			for(int z=1;z<=r;z++)
				add(chg(x,y,z),chg(x,y,z+1),v[x][y][z]);
			for(int z=D+1;z<=r+1;z++)
				for(int i=0;i<4;i++){
					int nx=x+dx[i],ny=y+dy[i];
					if(1<=nx&&nx<=p && 1<=ny&&ny<=q)
						add(chg(x,y,z),chg(nx,ny,z-D),INF);
				}
		}
//	print_edge();
	Dinic();
	cout<<ans<<endl;
	return 0;
}