最大流加强版，从 ID 算法到 LCT

· · 题解

Part1-Improved Dinic

ID（Improved Dinic) 算法是一种求最大流的高效算法，在随机图上复杂度为 O(km)，其中 k 是一个较小的常数，一般在 10 左右。缺点也很明显，加边离线，复杂度上限未知（可以理解为上限是 O(kn^2m)，但卡到 O(nm) 都不容易做到）。

ID 算法原理就是，对 Dinic 算法进行很多优化，最后不仅代码较短，效率也很高，值得一提的是，即使是小规模数据，他也能跑得比一般算法快。

具体优化如下：

  1. 当前弧（允许弧）优化；
  2. 分段加边优化；
  3. 先正后反（贪心初始流）优化；
  4. gap 优化。

当前弧（允许弧）优化大家都懂，分段加边优化是为了防止边权差异过大，因为 Dinic 算法只有在边权差异大时会跑得较慢。

贪心初始流是采用了二分图增广路算法的贪心初始匹配思想，先不连反边是为了不然反边影响初始效率，gap 优化可以参照 ISAP，AC 记录。

Part2-LCT-Dinic

这是一个最坏复杂度为 O(nm\log n) 的最大流算法。

把 ID 卡慢很简单，k 可以被卡到 \frac n3 左右，虽然通过此题的数据范围绰绰有余。

我们需要对 Dinic 的增广过程进行研究，考虑其之所以单次增广最坏为 O(nm) 是因为每一条增广路最多有 n 个点，由于可能每一条路有且仅有一条边满流，所以最多会增广 m 次。

发现一条边在一条增广路上如果没有满流，就还会继续扫到，这样对效率的影响极大，于是可以用数据结构来维护连边，断（零）边，链减（得到的流量），使用可爱的 LCT 十分合适，于是就这样愉快地决定啦！

由于单次增广每一条边最多只会加入一次，减少一次，每一次加入减少的复杂度都是平摊 O(\log n) 的，于是总复杂度为 O(nm\log n)。

加上 ID 的优化三（贪心初始流）就可以通过 luogu 数据了，并且速度比 ID 快一倍。

但是，在 UOJ 上会 TLE。

Part3-总结

其实 HLPP 的优势局限于本题的数据范围，再稠密点常数没有 MPM 小，再稀疏点就不如 LCT-Dinic。

以上 ID 的代码能通过 Luogu、LOJ、UOJ 的数据，但 LCT-Dinic 即使分段连边也通不过 UOJ 的第三十个测试点，而该点 ID 却能在 1ms 内通过，所以特殊构图能卡 LCT-Dinic，毕竟 LCT 常数大，且每次都有 \log，并且分段连边时答案变得飞快，根本没有一条一条 \log 增广的时间。

事实上，我还没见过有人在建模题上卡 Dinic，这就当整活图一乐了。