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

前言

“倍增流量阈值”的专业名称为 容量缩放（Capacity Scaling）。该优化应用于 Ford–Fulkerson 算法时，可获得

O(m^2 \log U)

的复杂度；若与 ISAP 结合，甚至能达到理论最优复杂度（但在算法竞赛中实用性不高）。实际上，将其引入 Dinic 算法也可得到

O(nm \log U)

的优良复杂度，且该优化代码改动量小，具有较高的实用价值。

算法流程

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

具体步骤如下：
设定一个流量阈值

T

，初始值不小于图中所有边的最大容量。

以阈值 $T$ $T$ 执行 Dinic 算法，要求每次增广时每条边的可用流量均不小于 $T$ $T$ 。
- 实现上只需在 Dinic 的 bfs 和 dfs 过程中忽略容量小于 $T$ 的边（通常只需调整几处判断条件）。
将 $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 算法编码简便、实际运行效率高的优点。因此，这是一种实用性强且易于实现的网络流优化方法。

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

文章操作

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

前言

算法流程

复杂度分析

总结

相关推荐

评论

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