自动搬运

查看原文

来自洛谷，原作者为

	EnofTaiPeople MGXS

搬运于2025-08-24 22:02:58，当前版本为作者最后更新于2021-11-09 11:51:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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，这就当整活图一乐了。