这种题按道理来讲，当前弧优化的 Dinic 应该是完全过不了的，应该只能用对偶图吧。
by Foreverxxx @ 2022-03-12 14:52:02
数据水。
by cnyzz @ 2022-03-12 15:28:40
@[hht2006](/user/175829) 比赛的时候也没有人这么做吧。
by Foreverxxx @ 2022-03-12 15:31:07
网络流时间复杂度极其玄学，尤其是在网络图这种比较特殊的图上，最小割往往就在源点或汇点附近，而且相同长度的增广路非常多，所以增广路算法跑得飞快。
而且你说的预流推进模板很明显用特殊图卡了增广路算法。原版数据下满优化 ISAP 不加读优都能跑进50ms，把 HLPP 吊着锤。
再举一个例子，费用流模板 $1 \le n \le 5 \times 10^3,1 \le m \le 5 \times 10^4$
随机数据下，最坏情况 $O(n^2m^2)$ 的MCMF最大的点跑了600ms。
by strcmp @ 2022-03-12 18:46:48
@[wql463](/user/551861) 是这个意思，Dinic 算法在处理一般的图的时候的优化是惊人的，只要没有经过特殊的构造，跑 $10^6$ 的数据通常不会出现问题。非常感谢！
by Foreverxxx @ 2022-03-19 16:03:04
@[Foreverxxx](/user/367316) 后排膜拜T神的思考
by Hasinon @ 2022-07-10 18:25:34
后排膜拜
by kexinluo @ 2023-01-10 15:06:00
@[kexinluo](/user/508834) %%%
by elswzl @ 2023-08-12 17:23:09