文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载本文系统讲解 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 年提出。无需任何数据结构的实现技巧改进版的一个巧妙之处在于选出最高高度顶点并不需要任何优先级队列、堆或多重集。实现采用了两条规则将所有当前高度最大且有溢出的顶点保存在一个普通列表vectorint current中该列表的刷新时机只有两种当列表中的所有顶点都被处理完后重新扫描生成新的列表此时剩下的自然都是高度较低的溢出顶点当某个顶点因relabel获得了一个比列表中现有顶点更高的新高度时立即用它重建列表。由于我们只需要当前最高高度而并非全局的严格有序结构这两条规则足以保证算法任何时刻取出的都是全局高度最大的溢出顶点。这种极简即正确的设计让代码保持了极高的可读性这正是仓库文档特意强调actually we dont need any data structures的原因。完整 C 实现与逐段解读以下代码来自 push-relabel-faster.md 的实现章节以{.cpp filepush_relabel_faster}标注仓库的测试流水线会通过 test/extract_snippets.py 将其自动提取为可编译的头文件const int inf 1000000000; int n; vectorvectorint capacity, flow; vectorint 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; } vectorint find_max_height_vertices(int s, int t) { vectorint 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, vectorint(n, 0)); excess.assign(n, 0); excess[s] inf; for (int i 0; i n; i) { if (i ! s) push(s, i); } vectorint 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主要依赖两个额外结构队列excess_vertices用于在 $O(1)$ 时间内取出下一个待处理的溢出顶点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 -stdc17 -fsanitizeundefined编译全部*.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 一节便于按主题串联阅读。赞分享文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载相关推荐Flow 索引访问类型Indexed Access Types完全指南T[K] 语法、可选索引访问与 $PropertyType 迁移Flow 索引访问类型Indexed Access Types完全指南 T K 语法、可选索引访问与 $PropertyType 迁移 本文是 Flow文档教程知识库cp-algorithms 详解最大流 MPM 算法O(V³) 的势能式阻塞流算法cp algorithms 详解最大流 MPM 算法O V³ 的势能式阻塞流算法 本篇文章围绕 cp algorithms 仓库中的 MPM 算法文档 htt文档教程知识库图搜索算法终极指南BFS广度优先搜索与DFS深度优先搜索详解图搜索算法终极指南BFS广度优先搜索与DFS深度优先搜索详解 图搜索算法是计算机科学和算法竞赛中的核心基础其中 广度优先搜索BFS 和 深度优先搜索D文档教程知识库上一篇google-research flood_forecasting 淹没建模算法解析基于 gauge 水位的阈值模型与流形模型实战指南下一篇CANN ops-transformer 算子解析aclnnScatterPaKvCache 接口详解与调用实战创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考