斜二倍增 x Dinic = O(VE \log^2 V)

yangzhe1990 · 2026-05-26 23:21:33 · 算法·理论

一、Dinic 算法的已知 O(VE \log V) 实现

网络流的 Dinic 算法中，做好残量网络的分层图 G_L 后，一条连通路对应一条增广路，选中一条增广路后，要做这些操作：

1. 计算增广路流量、找到边权恰好等于流量的一条边，这条边需要被删除；
2. 对于要删除的边，进行删除，将这条边的流量作为最终结果存储下来；删除掉的边对应的下一层结点，选择下一条边连向上一层，如果不存在边了，这个结点也需要删除，它到下一层结点的所有边也需要删除，影响的更下一层的结点也需要进行维护；
3. 将整条增广路（现在已经分成了两段）标记减小残量，实现为，对整条增广路的流做区间加法。

其中步骤 2、3 也可以换一个顺序进行操作。传统上用 Link-Cut Tree（下文缩写为 LCT ）做上面的操作，时间复杂度 O(E_L\log V)，E_L 是分层图 G_L 中的边数。

:::info[图及 URL] 动态树优化的 Dinic 最大流算法 这篇文章中的图（如下）很直观了。 也有洛谷的文章简述。 :::

用可并二叉树操作链，不考虑树结构

考虑其实是在做 DFS（并且有当前弧优化），找到了从源到汇的一条链。然后操作。之后删除掉边了以后，就断开了一截链。之后 DFS 选择了一条新的边的时候，如果是从中间连接到了某个之前断开了的链，就是把这个链再切一下，然后后面的部分连接上。（相当于 LCT 的 preferred-edge 切换的操作）

用可并二叉树实现 LCT：O(\log^2 V)

理论上讲，用任何一个可并平衡二叉树的结构维护每个链，等同于不用 Splay 而是其他的数据结构实现了 Link-Cut Tree。用 Splay 的好处在于它很随性，直接就等于实现了 LCT。

大神已经给我们证明了，如果用的不是 Splay，就是 O(\log^2 V) 的时间复杂度，因为 split、merge 操作的总和竟然是均摊 O(\log V) 的。

二、斜二倍增在分层图中是可并的

斜二倍增简介及原文：https://www.luogu.com.cn/article/u81tks5o

随便在什么地方竖着切开，发现坏掉的东西的规模是 O(\log L) 的，并且斜二倍增的特点就是前半段的合法性不受任何影响。L 代表层数，就是增广路长度的最大值。

切断的时候，不需要修坏掉的后缀部分，有区间加法标记的需要在断开前处理和下放，可能还要让它能够知道断在哪里了，相当于要对坏掉的部分做一个切开的具体高度的标记。

这里 G_L 的特点是分层图，合并的高度正好和之前切断的高度相同，因此斜二倍增可并。合并操作一定要按照先后顺序，哪里坏掉修哪里。前半段已经是另一条链、面目全非，也只需要修之前切断的时候坏掉的地方。

我们考虑这个问题：给一个斜二倍增的区间，切 k 次，最多可以弄坏几个地方。解应该是：最长的区间 1 次，次长的区间 2 次，4 次，依此类推，某个长度的区间数目大于 k 了，那就只能切坏 k 个。所以可以弄坏大约 k \log L - k\log k + k 个地方。那么合并 k 个段的总时间就是这个值。总时间不超过 K \log(LE_L/K) + K，知道总合并次数 K < 3E_L \log V，根据单调性知合并操作的总时间不超过 O(E_L \log V \log(L/\log V))。

综上，用斜二倍增优化 Dinic 算法

时间复杂度就是 O(VE \log^2 V)。考虑一下常数上的效率比 Link-Cut Tree 的提升，尽管 LCT 可以实现地常数很小很快，理论复杂度更高的斜二倍增实现效果也有可能更快。

实际上对数项 O(\log V \log(L/\log V)) 在最坏情况下会达到：可以设置一个满二叉树似的树形结构，然后每个点替换成一个长度为 M = O(L/\log V) 的链，假设 M < \sqrt{V}，层数是 O(M \log(V/M))，与 L 的规模相差不大。每次都可以选择一个终点，使得拼接次数是 O(\log(V/M))，相当于本问题中，每次增广路都是使得源点到上个终点的路径断开，选择这个终点。

但是这个结构下次的 G_L 可能就不同了，对于大一些的 L：直接令 M = \sqrt{V}，复杂度就是达到 O(\log^2 V) 的。

小优化？

p.s. Dinic 算法对于连接到汇的边好像是可以放松分层条件的。好像在后期放松了算法结束会快一点，在前期反而每轮变慢。如果放松了条件，寻找增广路之前预判一下到汇的连通性、去掉不连通的点和边好些。

每个点选择出边的时候，似乎用残量从大到小排序的顺序考虑（当前弧优化）流量增加速度会快，容易快点做完这一轮。

可以考虑先跑普通版的 Dinic 若干轮直到某轮的层数 L 满足 \sum{L_{pre}} + L \ge V \log V，省得一开始就折腾数据结构。

总结及其他

仔细回想一下，就是普通的 DFS 实现里面（非递归实现 DFS），突发奇想用斜二倍增去维护从源出发的容量、流量、最小边权，某条边满了切断、选择下一条边的时候，直接就用对数复杂度切开、接上了一个段（大家都设置了当前弧），而不是一层层向下走。实现起来非常的自然，竟然还有大神帮我们证明了拼接总次数是均摊 \log V 的，感觉非常神奇。DFS 中的其他步骤，例如结点完成遍历后作废、回溯，都均摊在 E_L 上了，不影响复杂度，也不涉及链的 split、merge 操作。

由于切开和接上的地方的深度是一致的，给人一种感觉是切开的时候什么都不需要标记，接上的时候自然就可以从最后一个结点开始向前跳跃，修好所有坏掉的地方，这样想是不对的，每个部分链，要严格记下链的终点、起点（接上的时候可能砍断了另一个链，需要找到起点，标记它新的终点）。

老年人没心思写代码，飘走。

朴素的 DFS 的时间复杂度摘要