题解：【模板】预流推进

背景

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

算法介绍

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

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

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

重标号（Relabel）：检查是否有结点 u 溢出（超额流不为零），且 ∀(u, v) ∈ E_f, h(u) ≤ h(v)，那么我们就要将 h(u) 更新为 min_{(u, v) ∈ Ef}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) ∈ 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 溢出，且 ∀(u, v) ∈ E_f, h(u) ≤ h(v)，那么我们就要将 h(u) 更新为 min_{(u, v) ∈ Ef}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²)（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²m)（Relabel 的 O(n²) 次操作与 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²)。

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

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

时间复杂度（理论）对比

时间复杂度

代码实现

#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;
}