@[FZzzz](/user/174045) 费用流复杂度为 $O(nmF)$,其中 $F$ 为最大流量。
by Smile_Cindy @ 2020-06-18 19:48:18
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-06-18 19:49:07
@[Alpha](/user/87058) 唔那这个题就更应该改了吧/kel
by FZzzz @ 2020-06-18 19:49:23
![](https://cdn.luogu.com.cn/upload/image_hosting/9v9shxp7.png)我又要炸掉一块板子么/kk
by LeavingZ @ 2020-06-18 19:49:43
还有这题似乎并没有说流量和费用的范围/fad
by FZzzz @ 2020-06-18 19:50:23
圈一下 @[EternalAlexander](/user/48355) ,神仙您怎么看?
by FZzzz @ 2020-06-18 19:56:08
出题人当然知道自己数据是用脚造的
所以只好扩大数据范围了
by Kubic @ 2020-06-18 20:03:22
@[Kubic](/user/119621) 这个倒是十分有道理((
by FZzzz @ 2020-06-18 20:15:03
这个东西比隔壁难,因为常见的基于最短路径增广的费用流(包括zkw)复杂度都是指数级的
by EternalAlexander @ 2020-06-18 20:17:17
@[FZzzz](/user/174045) 可以考虑限制一个最大流量
by EternalAlexander @ 2020-06-18 20:17:33