核心概述
Push–Relabel（Preflow-Push）最大流：基于“预流”和节点高度标签的最大流算法，反复在可行残量边上推送多余流量，不可推时提升高度；配合全局重标（global relabel）与 gap 启发能高效运行。最坏复杂度 O(V^3)，实际表现优良。
原文引述
Description: Maximum flow via push–relabel (preflow–push) with heuristics like global relabel and gap. Maintains excess and height labels; discharges active vertices by pushing along admissible edges or relabeling. Time: O(V^3) worst-case; much faster in practice with heuristics Status: tested
展开阐述
-
接口/数据结构（据实现）
- PushRelabel(n)：构造含 n 个点的流网络。
- addEdge(u, v, cap)：添加容量为 cap 的有向边，并加入反向边（容量 0）。
- maxFlow(s, t)：返回 s→t 的最大流量（64 位）。
- 常见内部字段：
- h[v]：高度标签（整数），初始 h[s]=n，h[其它]=0
- excess[v]：顶点 v 的多余流量
- g[v]：邻接边列表，边包含 to、rev、cap
- 选择策略：最高标号（highest label）或队列/桶维护活跃点
-
核心思路（预流 + 可行边 + 提升）
- 预流：先将源点 s 的可行边尽量饱和，产生中间顶点的 excess。
- 可行边（admissible）：残量边 (u→v) 满足 h[u]=h[v]+1。
- 推流（push）：沿可行边推送 Δ=min(excess[u], cap(u,v))；更新残量与 excess。
- 提升（relabel）：若 u 无可行边且 excess[u]>0，则令 h[u]=1+min{ h[v] | cap(u,v)>0 }。
- 排放（discharge）：对某活跃点 u 反复“推流或提升”，直到 excess[u]=0。
- 启发式：
- 全局重标（global relabel）：定期从 t 在反向残量上 BFS，重置 h 为到 t 的层距（不可达置为大值），显著降低无效尝试。
- gap 启发：若某高度 k 空缺，则对高度>k 的点可直接提到 ≥n+1 从而停用这些点。
- 最高标号优先：优先排放高度最大的活跃点，减少无效边扫描。
-
输出语义
- 返回值：最大流量。
- 若需恢复一个 s–t 最小割，可在终止时于残量图上从 s 做可达性，跨割边之和即最小割（见 074-图论-最小割）。
-
复杂度
- 理论最坏 O(V^3)；带启发常见速度与 057-图论-Dinic最大流 相当或更优，尤其在稠密图上表现出色。
-
使用与注意
- 容量使用 64 位以避免溢出；addEdge 必须添加反向边。
- 与 Dinic 相比，Push–Relabel 不依赖分层图；实现时注意 gap 与重标的触发频率。
- 结果与 074-图论-最小割 对偶；若涉及费用请改用 073-图论-最小费用最大流。