学了那么久网络流才发现自己不知道 Dinic 算法的一个在各边容量均为 \(1\) 的网络时复杂度上的结论。我说为啥学术社区那题优化建图复杂度是对的呢……
以下均认为使用了当前弧优化与多路增广。
以下认为 \(n\) 为点数，\(m\) 为边数，\(n=O(m)\)。
以下考虑的复杂度均为 \(O(\text{增广轮数}\times\text{单轮增广复杂度})\)，这个显然是一个合法上界。
一般网络：\(O(n^2m)\)
对于一般网络，增广轮数显然为 \(O(n)\)，因为每轮终点层数递增。
对于单轮增广复杂度，在不限制容量范围时，不会超过 \(O(nm)\)：对于每个状态的当前弧，只会消耗 \(O(n)\) 的时间找到一组合法增广路；而当前弧状态数不会超过 \(O(m)\)。
因此，对于一般网络，其复杂度为 \(O(n^2m)\)。
各边容量均为 \(1\) 的网络：\(O(m\min\{m^{\frac12},n^{\frac23}\})\)
接下来我们考虑的是各边容量均为 \(1\) 的网络。
对于单轮增广复杂度，考虑到每条边会被访问不超过一次，单轮复杂度为 \(O(m)\) 的。
增广轮数是 \(O(\sqrt m)\) 的：这个与单位网络的证明类似，下面会提到。
增广轮数是 \(O(n^{\frac23})\) 的：这个比较高明，推导比较复杂，咕了。
因此，对于各边容量均为 \(1\) 的网络，其复杂度为 \(O(m\min\{m^{\frac12},n^{\frac23}\})\)。
单位网络：\(O(m\sqrt n)\)
单位网络是一类特殊的各边容量均为 \(1\) 的网络，满足除源汇外各点入度不超过 \(1\) 或出度不超过 \(1\)。
显然单轮增广复杂度还是 \(O(m)\) 的。
考虑增广轮数。
如果在 \(\sqrt n\) 轮内已经结束，显然就是 \(O(\sqrt n)\) 的。
假设已经经过了 \(\sqrt n\) 轮，则到达汇点的增广路长度，也即在残量网络上的最短路长度，接下来不会低于 \(\sqrt n\)。
假设接下来几轮中我们还要流 \(d\) 条增广路，则由于单位网络中除源汇外每个点最多属于一条路，在当前残量网络中存在一种取 \(d\) 条路径（不是增广路）的方案。于是残量网络上起点到终点最短路为 \(O(\frac nd)\) 的。
因此，\(d=O(\sqrt n)\)，于是接下来最多再进行 \(d\) 轮增广。
因此增广轮数是 \(O(\sqrt n)\) 的。
因此，对于单位网络，其复杂度为 \(O(m\sqrt n)\)。
在稀疏图、稠密图上的分析
| 稀疏图（\(m\sim n\)） | 稠密图（\(m\sim n^2\)） | |
|---|---|---|
| 一般网络 | \(O(n^3)\) | \(O(n^4)\) |
| 各边容量均为 \(1\) 的网络 | \(O(n\sqrt n)\) | \(O(n^{\frac83})\) |
| 单位网络 | \(O(n\sqrt n)\) | \(O(n^{\frac52})\) |
在稀疏图上，各边容量均为 \(1\) 的网络的效率比较明显，\(n\) 可以取到 \(2\times10^5\) 左右。
在稠密图上，三者的差异就更大了。（不过复杂度一般卡不满）
标签：增广,复杂度,网络,sqrt,几种,轮数,各边,Dinic From： https://www.cnblogs.com/myee/p/dinic-algorithm.html