网络流与二分匹配
内容提要
本文梳理网络流算法：残量图描述如何改流，最小割证明最优性。介绍Ford-Fulkerson、Edmonds-Karp、Dinic、push-relabel与Hopcroft-Karp算法，强调整数容量、当前弧与gap启发式。核对NetworkX、OR-Tools、Boost源码，指出工程库多用push-relabel，近线性时间仍属理论前沿。
延伸解读
最大流算法必须提供割证书
文章强调，最大流算法不能只给出流量值，还必须同时输出一个最小割作为最优性证明。残量图负责描述如何修改流，而最小割证明无法再改进。工程调试时，这个证书比流量值本身更有用，因为它能验证算法正确性并帮助定位瓶颈。
路径选择策略决定算法效率
Ford-Fulkerson 框架中，增广路的选择至关重要。朴素 DFS 可能因容量大而增广次数多，甚至无理容量下不终止。Edmonds-Karp 通过每次选最短增广路，保证 O(VE^2) 时间；Dinic 则用分层图批量处理阻塞流，在单位容量图上表现接近 Hopcroft-Karp。
工程库普遍采用 push-relabel
文章核对源码发现，NetworkX 3.3 默认使用 preflow-push，OR-Tools v9.10 底层是 push-relabel，Boost 1.86 提供 highest-label push-relabel。这些实现依赖 global relabel、gap 等启发式。近线性时间算法仍是理论前沿，尚未成为通用库的默认选择。
复现实验应关注与时钟无关的计数
文章用增广次数、BFS/DFS 访问边数、push/relabel/gap 次数等指标比较算法，避免墙钟时间受系统负载影响。这些计数能揭示算法内部行为差异，但不能直接推断实际运行速度。真实性能比较还需固定图族、内存布局和编译选项。
Q&A
最大流算法结束后，如何证明当前流已经是最优的？
最大流算法结束时，从源点 s 在残量图中可达的点集 S 与补集 T 构成一个割 (S,T)。此时所有从 S 到 T 的边都被饱和，所有从 T 回到 S 的边流量为 0，因此流值等于割容量，根据最大流最小割定理，该流即为最大流。
Ford-Fulkerson 算法在什么情况下可能不终止？
当容量为无理数时，如果每次增广随意选择路径，Ford-Fulkerson 过程可能无限逼近最优值而不达到它。Zwick 1995 年的论文证明了存在这样的最小网络。
Dinic 算法中的当前弧优化是什么？为什么需要它？
当前弧优化是在 DFS 求阻塞流时，为每个顶点维护一个指针 it[u]，记录下一条待检查的边。当某条边被证明不能继续通向汇点后，本轮阻塞流内不会再从同一个顶点重复扫描它。这避免了重复检查无效边，否则 Dinic 在稠密图上的常数会膨胀得很快。
Push-relabel 算法中的 gap 启发式有什么作用？
gap 启发式是指：若某个高度 k 已经没有顶点，那么高度大于 k 且小于顶点总数的顶点不可能再到达汇点，可以整体抬到“无穷高”附近，之后把多余预流推回源点方向。这能加速算法收敛。
如何将二分图最大匹配问题归约为最大流问题？
添加源点 s 和汇点 t；对每个左侧顶点 u 加边 (s,u) 容量 1；对每条二分边 (u,v) 加边 (u,v) 容量 1；对每个右侧顶点 v 加边 (v,t) 容量 1。整数容量最大流存在整数最优解，因此流值等于匹配大小。
Hopcroft-Karp 算法与 Dinic 算法在二分匹配上的关系是什么？
Hopcroft-Karp 不显式建流网络，但做的是同一件事的特化：BFS 从所有未匹配的左侧顶点出发构造交替分层，DFS 在最短交替路上找一组点不相交的增广路并同时翻转。每一阶段为 O(E)，阶段数为 O(√V)，总时间 O(E√V)。Dinic 在单位容量二分图上行为与 Hopcroft-Karp 非常接近。
NetworkX、OR-Tools 和 Boost 这些库默认使用哪种最大流算法？
NetworkX 3.3 默认使用 preflow_push（push-relabel 的一种）；OR-Tools v9.10 的 SimpleMaxFlow 底层是 push-relabel 实现；Boost 1.86 提供 highest-label push-relabel 算法，但并非默认。这些库大多采用 push-relabel 及其启发式。
近线性时间最大流算法是否已经应用于生产环境？
没有。Chen 等人在 FOCS 2022 提出的近线性时间最大流算法是理论前沿，针对多项式有界整数容量，运行时间为 m^{1+o(1)}。但常见工程库仍采用更传统、易实现、常数可控的算法，如 Dinic 或 push-relabel。
