企业官网建设流程全解析

• 文档
• 教程
• 知识库

本文系统讲解 cp-algorithms 仓库中 push-relabel-faster.md 所记录的改进版 push-relabel（预流推进）算法：在保持算法整体框架不变的前提下，通过「始终处理高度最大的溢出顶点」这一极小修改，将复杂度从基础版的 $O(V^2E)$ 显著降低到 $O(VE + V^2\sqrt{E})$（最坏情况 $O(V^3)$）。读完本文，你将掌握改进策略背后的原理、无需复杂数据结构的实现技巧，以及可直接运行的 C++ 源码与仓库内置的测试验证方式。

背景：从基础版 push-relabel 算法说起

改进版是对基础版 push-relabel 算法 的一次针对性优化，因此理解改进的前提是理解基础版的三个核心概念：

预流（preflow）。与普通流不同，预流允许某个顶点"只进不出"——它收到多少流，就可以不一定全部转发出去。对于每条边 $e$，预流只需满足 $0 \le f(e) \le c(e)$，以及对于每个非源点非汇点顶点，入流量可以大于等于出流量。我们把"多收进来、尚未送出去"的流量称为溢出量（excess），记作 $x(u) = \sum_{(v,u)\in E} f((v,u)) - \sum_{(u,v)\in E} f((u,v))$。如果除了源点 $s$ 和汇点 $t$ 以外的所有顶点溢出量都为零，那么预流就自动成为一个合法流。

高度标记（labeling / height function）。算法为每个顶点维护一个整数高度 $h$，要求满足：$h(s) = |V|$、$h(t) = 0$，且对残量网络中的每条边 $(u,v)$（即 $u$ 可以向 $v$ 继续推进流量）都有 $h(u) \le h(v) + 1$。这样设置有一个关键推论：只要存在合法的高度标记，残量网络中就不存在从 $s$ 到 $t$ 的增广路径——因为一条增广路径最多有 $|V|-1$ 条边，每条边最多把高度降低 1，不可能从 $h(s)=|V|$ 一路降到 $h(t)=0$。于是算法终止时得到的流必然是最优的。

两种基本操作。算法在每次迭代中执行：

• push(u, v)：把溢出从 $u$ 推送到相邻顶点 $v$，规则是只能向高度恰好低 1 的顶点推送（$h(u) = h(v) + 1$），推送量至多为 $\min(x(u),\ c((u,v)) - f((u,v)))$；
• relabel(u)：当 $u$ 有溢出却无法推给任何相邻顶点时，把 $u$ 的高度抬高到"其所有可推进邻点中最低高度 + 1"，从而重新满足合法标记。

基础版的朴素实现从源点 $s$ 出发把所有出边灌满（即 $f((s,u)) = c((s,u))$，同时令 $h(s)=|V|$、其余顶点高度为 0）来获得一个合法预流，然后反复执行 push / relabel，直到没有可操作的溢出顶点为止。其总复杂度为 $O(V^2E)$。

核心改进：始终处理最高高度的顶点

基础版中，每轮选择哪个溢出顶点来执行 push / relabel没有任何特定规则——通常的做法是用一个队列保存所有溢出顶点（详见 push-relabel.md 的基础实现）。

而改进版只修改了这一点：

始终选择**高度最大（greatest height）**的溢出顶点，对它执行 push 与 relabel 操作。

直觉上，高度标记天然刻画了顶点距离汇点的远近：高度越高意味着离汇点越远，也越接近源点一侧。优先处理最高高度的顶点，可以让流量以更"有序"的方式向下坡方向推进，从而大幅压缩无谓的 push 次数。这一修改极其简单，但对复杂度的影响巨大：

$$O(VE + V^2\sqrt{E})$$

当图较稠密时（$E$ 接近 $V^2$），该上界退化为最坏情况 $O(V^3)$；而基础版是 $O(V^2E)$，在稠密图上量级相同，但在稀疏图上改进版优势明显。该改进由Cheriyan 和 Maheshwari 于 1989 年提出。

无需任何数据结构的实现技巧

改进版的一个巧妙之处在于：选出"最高高度顶点"并不需要任何优先级队列、堆或多重集。实现采用了两条规则：

1. 将所有"当前高度最大且有溢出"的顶点保存在一个普通列表（vector<int> current）中；
2. 该列表的刷新时机只有两种：
   • 当列表中的所有顶点都被处理完后，重新扫描生成新的列表（此时剩下的自然都是高度较低的溢出顶点）；
   • 当某个顶点因relabel获得了一个比列表中现有顶点更高的新高度时，立即用它重建列表。

由于我们只需要"当前最高高度"而并非全局的严格有序结构，这两条规则足以保证：算法任何时刻取出的都是全局高度最大的溢出顶点。这种"极简即正确"的设计让代码保持了极高的可读性，这正是仓库文档特意强调"actually we don't need any data structures"的原因。

完整 C++ 实现与逐段解读

以下代码来自 push-relabel-faster.md 的实现章节（以{.cpp file=push_relabel_faster}标注，仓库的测试流水线会通过 test/extract_snippets.py 将其自动提取为可编译的头文件）：

const int inf = 1000000000; int n; vector<vector<int>> capacity, flow; vector<int> height, excess; void push(int u, int v) { int d = min(excess[u], capacity[u][v] - flow[u][v]); flow[u][v] += d; flow[v][u] -= d; excess[u] -= d; excess[v] += d; } void relabel(int u) { int d = inf; for (int i = 0; i < n; i++) { if (capacity[u][i] - flow[u][i] > 0) d = min(d, height[i]); } if (d < inf) height[u] = d + 1; } vector<int> find_max_height_vertices(int s, int t) { vector<int> max_height; for (int i = 0; i < n; i++) { if (i != s && i != t && excess[i] > 0) { if (!max_height.empty() && height[i] > height[max_height[0]]) max_height.clear(); if (max_height.empty() || height[i] == height[max_height[0]]) max_height.push_back(i); } } return max_height; } int max_flow(int s, int t) { height.assign(n, 0); height[s] = n; flow.assign(n, vector<int>(n, 0)); excess.assign(n, 0); excess[s] = inf; for (int i = 0; i < n; i++) { if (i != s) push(s, i); } vector<int> current; while (!(current = find_max_height_vertices(s, t)).empty()) { for (int i : current) { bool pushed = false; for (int j = 0; j < n && excess[i]; j++) { if (capacity[i][j] - flow[i][j] > 0 && height[i] == height[j] + 1) { push(i, j); pushed = true; } } if (!pushed) { relabel(i); break; } } } return excess[t]; }

关键环节说明：

• 全局状态（n、capacity、flow、height、excess）与基础版一致，使用 $O(V^2)$ 的邻接矩阵存储容量与流量，适合讲解原理；生产级代码可按仓库中 Dinic 算法 的边表结构改造。
• find_max_height_vertices(s, t)：单次线性扫描，找出所有"有溢出且高度最高"的顶点；一旦发现更高者就清空列表（对应上文提到的第二种刷新时机）。由于每次只会返回相等最高高度的顶点集合，逐个处理时不会破坏"最高优先"的语义。
• max_flow(s, t)的初始化与基础版完全相同：height[s] = n、excess[s] = inf，然后把源点的所有出边一次性推满。
• 主循环：反复取得当前最高高度顶点列表；对每个顶点尝试向所有高度低 1 且有残量容量的邻点 push；若一轮扫描后该顶点仍有溢出且无处可推（pushed == false），立即relabel并break，让外层循环重新计算最高高度顶点集。这正是保证"每轮处理的都是全局最高高度顶点"的关键编排。
• 返回值：算法结束时源点和汇点之外的所有溢出都已被清空，excess[t]即汇聚到汇点的流量总和，也就是最大流值。

与基础版实现的差异对比

基础版实现（见 push-relabel.md）主要依赖两个额外结构：

1. 队列excess_vertices：用于在 $O(1)$ 时间内取出下一个待处理的溢出顶点；
2. current-arc（当前弧）优化：维护每个顶点上一次扫描到的邻接边位置，让顶点在某个高度值下只切换 $O(n)$ 次边，从而保证总复杂度不劣化。

而改进版通过"按高度排序处理"这一全局策略，同时消除了对队列和 current-arc 的需求——这正是该版本代码更短、结构更清晰的原因。值得注意的是，基础版中的discharge（用 while 循环把单个顶点的溢出清空）在改进版中也被展开成了主循环内的 for 扫描，配合break实现"遇到死路立即 relabel 并换最高顶点处理"。

复杂度证明的直觉与上界

改进版复杂度 $O(VE + V^2\sqrt{E})$ 的得来并非巧合。沿用基础版的分析框架：顶点高度最大为 $2|V|-1$，因此 relabel 次数被限制在 $O(V^2)$ 以内（基础版证明，见 push-relabel.md 的 Complexity 一节）；饱和 push（单次推满整条边容量）的次数上界为 $O(VE)$。改进点在于非饱和 push：因为始终优先处理最高高度顶点，非饱和 push 的次数从基础版的 $O(V^2E)$ 被压缩到 $O(V^2\sqrt{E})$，三项相加即得总复杂度 $O(VE + V^2\sqrt{E})$。在边数 $E$ 接近 $V^2$ 的稠密图上，该表达式约为 $O(V^3)$，与仓库中 MPM 算法（$O(V^3)$）处于同一量级。

仓库实测：测试用例与验证方式

改进版代码在仓库中是被实际编译运行验证过的，而非仅停留在文档层面：

• 测试用例test/test_push_relabel_faster.cpp 遍历test/data/flow_networks.h中定义的所有流网络，用assert(max_flow(fn.source, fn.sink) == fn.maxflow)校验结果。
• 测试数据test/data/flow_networks.h 内置了 6 组网络，包括 cp-algorithms 文档示例（最大流 10）、维基百科 Edmonds-Karp 示例（最大流 5）、对 Ford-Fulkerson 最坏的 4 顶点网络（最大流 2000）、brilliant.org 示例（最大流 23）以及来自斯坦福课堂资料的网络（最大流 28）。
• 构建方式：test/test.sh先调用test/extract_snippets.py从src/目录的 Markdown 文档中提取{.cpp file=...}代码块生成.h头文件，再以g++ -std=c++17 -fsanitize=undefined编译全部*.cpp并运行。这意味着 push-relabel-faster.md 中的这段源码与基础版、Dinic、MPM 等实现共用同一套基准测试数据，可直接交叉验证正确性。

适用场景与后续阅读

改进版 push-relabel 适合作为通用最大流求解器的默认候选：它实现极短、无需复杂数据结构，且在稀疏图上优于 $O(V^2E)$ 的基础版。需要指出的是，其复杂度中 $\sqrt{E}$ 一项使它在极稠密图上的表现与 Dinic（$O(V^2E)$，见 dinic.md）各有侧重；实际竞赛与工程中，也常把本算法与 Dinic 算法、MPM 算法、Edmonds-Karp 算法 按图规模与实现复杂度灵活选用。若对最大流问题的形式化定义、残量网络与增广路径不熟悉，建议先阅读 Ford-Fulkerson 与 Edmonds-Karp；需要配套的带下界流问题求解时，可参考 flow_with_demands.md 中对 push-relabel 的直接调用示例。相关文档在 src/navigation.md 中被编排在 "Flows and related problems" 一节，便于按主题串联阅读。

• 文档
• 教程
• 知识库