0
2300770111 @ 2025-10-22 16:23:43
题解

思路分析

这是一道经典的 最小割 + 网络流 的三维网格切割问题。

问题建模
- 在 $P \times Q \times R$ 的三维网格中选择切面
- 切面是函数 $f(x, y)$ ，表示每个纵轴的切割高度
- 相邻纵轴的切割高度差 $\leq D$
- 最小化切割点的不和谐值之和
核心思路

1. 最小割建模

这是一个经典的闭合子图问题，可以转化为最小割。

将三维空间看作分层图：
- 每个点 $(x, y, z)$ 拆成一个节点
- 选择切面等价于在每个纵轴上选择一个高度
2. 网络流构图（关键）

核心思想：将切面问题转化为最小割。

建图原理：
- 每个纵轴 $(x, y)$ 必须选择恰好一个高度 $z$ 作为切割点
- 选择高度 $z$ 意味着切断该纵轴在 $z$ 和 $z+1$ 之间的"连接"
- 所有选择的切割点构成一个"割"
具体构图：
1. 纵轴内部（ $P \times Q$ 个纵轴）：
  
  对每个 $(x, y)$ ，创建节点 $(x,y,1), (x,y,2), \ldots, (x,y,R+1)$
  
  连边： $(x,y,z) \xrightarrow{v(x,y,z)} (x,y,z+1)$ （ $z = 1 \sim R$ ）
  
  割掉这条边 $\Leftrightarrow$ 选择 $z$ 作为切割高度
2. 源点和汇点：
  
  $S \xrightarrow{\infty} (x,y,1)$ （所有纵轴的底部）
  
  $(x,y,R+1) \xrightarrow{\infty} T$ （所有纵轴的顶部）
  
  保证每个纵轴都被"切穿"
3. 相邻纵轴约束（保证光滑性 $|f(x,y) - f(x',y')| \leq D$ ）：
  
  如果 $|x-x'| + |y-y'| = 1$ （曼哈顿距离为1）
  
  连边： $(x,y,z+D) \xrightarrow{\infty} (x',y',z)$ （ $z = D+1 \sim R+1$ ）
  
  含义：如果 $(x,y)$ 在 $z+D$ 或更高处，则 $(x',y')$ 不能在 $z$ 以下
  
  等价于： $f(x,y) \geq z+D \Rightarrow f(x',y') \geq z$ ，即 $f(x,y) - f(x',y') \leq D$
为什么是最小割？
- 每个纵轴必须恰好割一条边（选择切割高度）
- 相邻约束边容量为 $\infty$ ，不会被割
- 最小割 = 最小切割代价
3. Dinic 求最小割

使用 Dinic 算法求最小割，即为最小总不和谐值。

算法步骤
1. 建图：
  
  创建 $P \times Q \times (R+2)$ 个节点
  
  添加源点和汇点
  
  按规则连边
2. Dinic 算法：
  
  BFS 分层
  
  DFS 增广
  
  求最大流（= 最小割）
3. 输出答案
复杂度分析
- 节点数： $O(PQR)$
- 边数： $O(PQR)$
- Dinic 时间复杂度： $O(V^2E)$
- 总时间复杂度： $O((PQR)^2)$
- 空间复杂度： $O(PQR)$
```
#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;
}
```

2300770111 @ 2025-10-17 18:48:02

题解

把切面看成从柱状体中挑选出每根纵轴的一个高度，同时对相邻纵轴施加 “高度差不超过 $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;
}

ID

3259

时间

3000ms

内存

256MiB

难度

标签

递交数

已通过

上传者

2300770111

2 条题解

题解

思路分析

问题建模

核心思路

算法步骤

复杂度分析

题解

「HNOI2013」切糕

信息