较为实用的快速网络流——倍增流量阈值优化Dinic

· · 算法·理论

容量缩放优化在 Dinic 算法中的应用

前言

“倍增流量阈值”的专业名称为 容量缩放（Capacity Scaling）。该优化应用于 Ford–Fulkerson 算法时，可获得 O(m^2 \log U) 的复杂度；若与 ISAP 结合，甚至能达到理论最优复杂度（但在算法竞赛中实用性不高）。实际上，将其引入 Dinic 算法也可得到 O(nm \log U) 的优良复杂度，且该优化代码改动量小，具有较高的实用价值。

算法流程

本算法基于 Dinic 算法实现，建议先掌握 Dinic 求解最大流的基本方法。

具体步骤如下：
设定一个流量阈值 T，初始值不小于图中所有边的最大容量。

  1. 以阈值 T 执行 Dinic 算法，要求每次增广时每条边的可用流量均不小于 T。
    • 实现上只需在 Dinic 的 bfs 和 dfs 过程中忽略容量小于 T 的边（通常只需调整几处判断条件）。
  2. 将 T 更新为 T/2，重复上述步骤，直至 T < 1。

复杂度分析

设当前轮次的阈值为 T，当前残量网络的最大流值为 F_T。
定义点集 A 为从源点出发，仅经过可用流量 f \ge 2T 的边所能到达的所有顶点，其余顶点属于点集 B。

考虑割 c(A, B)：所有连接 A 与 B 的边，其可用流量均小于 2T（否则可以继续向外扩展 A 集合）。因此割的容量满足：

c(A, B) < 2T \cdot m

注意：由于之前已处理过更大的阈值，汇点不可能位于 A 中，因此上述构造确实形成一个合法割。

根据最大流最小割定理：

F_T = C_T \leq c(A, B) < 2Tm

我们得到了当前轮次最大流的上界。由于每轮中一次增广至少推送 T 的流量，因此该轮增广次数不超过：

\frac{2Tm}{T} = 2m

Dinic 算法中单次增广的复杂度为 O(n)，故每一轮（即一个阈值 T 对应的完整 Dinic 执行）的总复杂度为 O(nm)。

阈值 T 每次减半，总共迭代 O(\log U) 轮，因此整体复杂度为：

O(nm \log U)

其中 U 为图中最大边权，n 为点数，m 为边数。

总结

容量缩放优化无需大幅改动原有 Dinic 框架，即能将复杂度降至 O(nm \log U)，同时保留了 Dinic 算法编码简便、实际运行效率高的优点。因此，这是一种实用性强且易于实现的网络流优化方法。