@[Scultura_Zhao](/user/86624) 写过这么多费用流题了,我写的一直是 EK,没被卡过
学完费用流这么久了,我还是不会分析费用流复杂度,好像跟流量有关
by 81179332_ @ 2020-08-10 21:58:52
话说最大流的数据范围都改了为什么这题还不改?
by Gemini7X @ 2020-08-10 22:01:56
费用流EK和Dinic都不卡吧
by _lgswdn @ 2020-08-10 22:05:52
EK和Dinic都不卡
by Ryo_Yamada @ 2020-08-10 22:06:10
EK和Dinic都卡(
by Gemini7X @ 2020-08-10 22:11:32
@[81179332_](/user/53994) 复杂度为 $O(nmF)$,如果使用Dijkstra那么复杂度为 $O(nm+mF\log n)$
by Smile_Cindy @ 2020-08-10 22:20:09
其中 $n$ 为点数, $m$ 为边数, $F$ 为最大流流量。
by Smile_Cindy @ 2020-08-10 22:20:37
@[Alpha](/user/87058) 谢谢您,这是把 SPFA 卡满的复杂度嘛
by 81179332_ @ 2020-08-10 22:21:44
@[Alpha](/user/87058) 跪求复杂度推导
by 洛谷Onlinejudge @ 2020-08-10 22:42:52
@[Scultura_Zhao](/user/86624) @[81179332_](/user/53994)
[here](https://ouuan.github.io/post/%E5%9F%BA%E4%BA%8E-capacity-scaling-%E7%9A%84%E5%BC%B1%E5%A4%9A%E9%A1%B9%E5%BC%8F%E5%A4%8D%E6%9D%82%E5%BA%A6%E6%9C%80%E5%B0%8F%E8%B4%B9%E7%94%A8%E6%B5%81%E7%AE%97%E6%B3%95/)
by Smile_Cindy @ 2020-08-11 09:20:35