题解：【模板】预流推进

背景

我们注意到其他的网络流算法都是 $O(n^2m)$，$(n^3)$ 或 $O(nm^2)$ 等的时间复杂度上界，太大了，有没有更加紧凑的时间复杂度上界呢？有的，兄弟有的，HLPP 时间复杂度为 $O(n^2m^{\frac{1}{2}})$，快多了，而且在随机图中也不会太劣于 Dinic 或者 ISAP。

算法介绍

我们现在允许流量在非源汇点的节点中暂时存储（我们将存储在非源汇点中的流称作这个点的超额流），同时定义以下操作：

设置一个高度函数 $h(x)$，初始值除了源点 $s$ 为 $n$ 以外，其余都通过 BFS 求解初始值：从 $t$ 到 $s$ 反向 BFS，使每个点有一个初始高度（它到汇点的距离）。

推流（Push）：如果结点 $u$ 溢出（超额流不为零），且存在结点 $v((u,v)\in E_f,c(u,v)-f(u,v)>0,h(u)=h(v)+1)$，那么我们尽可能将超额流从 $u$ 流向 $v$，如果 $(u,v)$ 在推送完之后满流，将其从残量网络中删除。

重标号（Relabel）：检查是否有结点 $u$ 溢出（超额流不为零），且 $\forall (u,v)\in E_f,h(u)\leq h(v)$，那么我们就要将 $h(u)$ 更新为 $\min_{(u,v)\in E_f}h(v)+1$。

主要流程：

  1. 先从 $t$ 到 $s$ 反向 BFS，使每个点有一个初始高度（它到汇点的距离）。
  2. 从 $s$ 开始向外推流，将有超额流的点放入优先队列。
  3. 不断从优先队列里取出高度最高的点进行推流操作。
  4. 若推完还有超额流，更新高度标号，重新放入优先队列。
  5. 当优先队列为空时结束算法，最大流即为 $t$ 的超额流。

图解如下：

算法图解

gap 优化：如果某个高度不存在，为什么我们就不继续算了，直接将所有比该高度高的节点标记为不可到达（使它的高度为 $n+1$，这样就会直接向 $s$ 推流了）。

正确性证明

首先，因为求的是最大流，所以我们最直观的想法就是管它能不能塞那么多，源点直接全部流出去。预流推进算法的思想就是，允许流量在非源汇点的节点中暂时存储（我们将存储在非源汇点中的流称作这个点的超额流），同时伺机将自身的超额流通过管道推送出去。只要保证在算法结束后所有非源汇点的超额流都为 $0$，那么这种方案就是合法的。

考虑一个朴素的算法，我们设置一个高度函数 $h(x)$，初始值除了源点 $s$ 为 $n$ 以外，其余初始值都为 $0$。

推流：如果结点 $u$ 溢出，且存在结点 $v((u,v)\in E_f,c(u,v)-f(u,v)>0,h(u)=h(v)+1)$，那么我们尽可能将超额流从 $u$ 推送到 $v$，推送过程中我们只关心超额流和 $c(u,v)-f(u,v)$ 的最小值，不关心 $v$ 是否溢出，如果 $(u,v)$ 在推送完之后满流，将其从残量网络中删除。

具体的呢，就是如下操作：

  1. 先从 $s$ 向周围点推流（把该点的超额流推给周围点，注意：推的流量不能超过边的容量也不能超过该点超额流），并让周围点入队。（注意：$s$ 和 $t$ 不能入队）

  2. 不断地取队首元素，对队首元素推流。

  3. 队列为空时结束算法，$t$ 点的超额流即为最大流。

同时，我们在过程中要检查是否有结点 $u$ 溢出，且 $\forall (u,v)\in E_f,h(u)\leq h(v)$，那么我们就要将 $h(u)$ 更新为 $\min_{(u,v)\in E_f}h(v)+1$。

为什么这样就不会出现来回推流的情况了呢？

当两个点开始来回推流时，它们的高度会不断上升，当它们的高度大于 $s$ 时，会把超额流还给 $s$。

所以在开始预流推进前要先把 $s$ 的高度改为 $n$（点数），免得一开始 $s$ 周围那些点就急着把超额流还给 s。

时间复杂度

对于暴力扫描策略按固定顺序遍历顶点，对每个顶点执行 Push 或 Relabel 操作的暴力算法。其时间复杂度主要由以下两部分决定：

1. Relabel 操作的次数

每个顶点 $u$ 的高度 $h(u)$ 初始为 $0$，每次 Relabel 操作后 $h(u)$ 严格递增（设为相邻顶点最小高度 + 1），且 $h(u)$ 的最大值不超过 $2n$（当顶点无法向汇点推送时，其高度最终会被抬高至 $n+1$，回流至源点）。因此，每个顶点最多被 Relabel $O(n)$ 次，总 Relabel 次数为 $O(n^2)$（$n$ 为顶点数）。

2. Push 操作的次数

对于每条边 $(u, v)$，每次 Push 操作会减少其残量容量。当边 $(u, v)$ 的残量容量为 $0$ 时，需等待 $u$ 或 $v$ 被 Relabel（$h(u)$ 或 $h(v)$ 改变）后才可能再次被推送。由于 $h(u)$ 和 $h(v)$ 的变化次数均为 $O(n)$，每条边最多被 Push $O(n)$ 次。总边数为 $m$，因此总 Push 次数为 $O(nm)$。

综上，暴力扫描策略的时间复杂度为 $O(n^2m)$（Relabel 的 $O(n^2)$ 次操作与 Push 的 $O(nm)$ 次操作的乘积，单次操作时间为 $O(1)$）

HLPP 在此基础上的优化

HLPP 通过优先处理高度最高的活跃顶点（使用桶结构按高度分层管理），避免了暴力扫描中的无效推送，将时间复杂度优化至 $O(n^2\sqrt{m})$。其推导核心如下：

1. 高度分层与桶结构的作用

HLPP 维护一个桶数组，每个桶对应一个高度值，存储该高度下的所有活跃顶点（超额流非零的顶点）。每次选择当前最高高度的桶中的顶点进行处理，确保流量优先向低高度层传递，减少“乒乓推送”（两个顶点反复互相推送）的可能。

2. 关键引理：边的推送次数限制

通过分析高度函数的变化规律，可证明每条边 $(u,v)$ 最多被 Push $O(\sqrt{m})$ 次。假设顶点 $u$ 的高度为 $h$，顶点 $v$ 的高度为 $h-1$（满足推送条件），则当 $u$ 向 $v$ 推送后，$v$ 的高度可能因后续 Relabel 操作而增加，但 HLPP 优先处理高高度顶点，使得 $v$ 的高度不会频繁低于 $u$ 的高度，从而限制了同一条边的重复推送次数。

3. 总操作次数的优化

  • Relabel 操作次数：每个顶点的高度最多增加 $O (n)$ 次，总次数仍为 $O (n^2)$。

  • Push 操作次数：每条边最多被 Push $O (\sqrt{m})$ 次，总次数为 $O (m\sqrt{m})$。

总而言之，HLPP 的时间复杂度优化为 $O(n^2\sqrt{m})$，显著优于暴力扫描的 $O(n^2m)$。

时间复杂度（理论）对比

时间复杂度

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;
struct Edge {
	int v, w, nxt;
}edge[2500000 + 10];
int head[12000 + 10], idx = 1;
void add(int u, int v, int w) {
	edge[++idx] = { v,w,head[u] };
	head[u] = idx;
}
void addedge(int u, int v, int w) {
	add(u, v, w); add(v, u, 0);
}
int h[12000 + 10], more[12000 + 10], g[12000 + 10];
struct _ { bool operator()(int a, int b) { return h[a] < h[b]; } };
priority_queue<int, vector<int>, _> pq;
bool vis[12000 + 10];
void bfs(int t) {
	memset(h, 0x3f, sizeof h);
	queue<int>q; h[t] = 0; q.push(t);
	while (!q.empty()) {
		int now = q.front(); q.pop();
		for (int i = head[now]; i; i = edge[i].nxt)
			if (edge[i ^ 1].w && h[edge[i].v] > h[now] + 1)
				h[edge[i].v] = h[now] + 1, q.push(edge[i].v);
	}
}
void push(int now, int s, int t) {
	for (int i = head[now]; i; i = edge[i].nxt) {
		if (edge[i].w && h[edge[i].v] + 1 == h[now]) {
			int flow = min(more[now], edge[i].w);
			more[edge[i].v] += flow; more[now] -= flow;
			edge[i].w -= flow; edge[i ^ 1].w += flow;
			if (edge[i].v != s && edge[i].v != t && !vis[edge[i].v])
				vis[edge[i].v] = 1, pq.push(edge[i].v);
			if (more[now] == 0) return;
		}
	}
}
void relabel(int now) {
	h[now] = INT_MAX;
	for (int i = head[now]; i; i = edge[i].nxt)
		if (edge[i].w && h[edge[i].v] + 1 < h[now])
			h[now] = h[edge[i].v] + 1;
}
int hlpp(int n, int s, int t) {
	bfs(t);
	if (h[s] == 0x3f3f3f3f) return 0;
	h[s] = n;
	for (int i = 1; i <= n; ++i) if (h[i] ^ 0x3f3f3f3f) g[h[i]]++;
	for (int i = head[s]; i; i = edge[i].nxt)
		if (int w = edge[i].w; w)
			edge[i].w -= w, edge[i ^ 1].w += w, more[s] -= w, more[edge[i].v] += w,
			edge[i].v != s && edge[i].v != t && !vis[edge[i].v] ? vis[edge[i].v] = 1, pq.push(edge[i].v) : void();
	while (!pq.empty()) {
		int now = pq.top(); pq.pop(); vis[now] = 0; push(now, s, t);
		if (more[now])
			if ((h[now] ^ 0x3f3f3f3f)) {
				if (!--g[h[now]])
					for (int i = 1; i <= n; i++)
						if (i != s && i != t && h[i] > h[now] && h[i] < n + 1)
							h[i] = n + 1;
				relabel(now); ++g[h[now]], pq.push(now), vis[now] = 1;
			}
	}
	return more[t];
}
int n, m, s, t;
signed main() {
	cin.tie(0)->sync_with_stdio(false);
	cin >> n >> m >> s >> t;
	for (int i = 1, u, v, w; i <= m; ++i) {
		cin >> u >> v >> w; addedge(u, v, w);
	}
	cout << hlpp(n, s, t) << endl;
	return 0;
}
#题解 #网络流
题解：【模板】预流推进
https://lzj-blog.top/2025/05/20/题解：【模板】预流推进/
作者
starfallen
发布于
2025年5月20日
许可协议