@[ouuan](/space/show?uid=49742) 建议出一个：【模板】最小费用最大流加强版
by 闹闹、 @ 2019-10-29 19:09:14
@[WAPERVAPES](/space/show?uid=72419) 是说，这个题的数据范围给的不对，能过是因为没跑满
by yurzhang @ 2019-10-29 19:09:28
另外zkw费用流也是假的复杂度吗
by 闹闹、 @ 2019-10-29 19:09:39
orz ouuan
by EternalAlexander @ 2019-10-29 19:10:23
资瓷
by EMT__Mashiro @ 2019-10-29 19:11:13
@[WAPERVAPES](/space/show?uid=72419) OI 界中叫做 Dinic 和 EK 的那两个最大流算法，把其中的 BFS 改成求最短路，复杂度都是与值域多项式相关的，即复杂度是伪多项式的。
多项式复杂度有弱多项式和强多项式两种，弱多项式就是关于输入长度（$n$、$m$ 之类的，以及 $\log$ 值域）为多项式复杂度，强多项式就是在加减乘除为 $O(1)$ 时复杂度关于数据规模为多项式（就是说跟值域完全无关，只和 $n$, $m$ 之类的相关，复杂度关于 $n$, $m$ 之类的为多项式）。
另外我那篇博客里提到的弱多项式复杂度算法也是 EK 提出的，但不是常见的那种上界为 $O(nm^2)$ 的 EK 最大流算法。
不知道您是怎么读成“Dinic跑最短路是错的，然后EK时间复杂度不对”的...
by ouuan @ 2019-10-29 19:12:47
@[Spfa](/space/show?uid=149462) 您可以在 [Min_25 的博客](https://min-25.hatenablog.com/entry/2018/03/19/235802) 中看到 "zkw-algorithm"...我个人不是很了解 zkw 费用流。
by ouuan @ 2019-10-29 19:14:28
出加强版也是可以的，但与修正此题数据范围是两回事（
by ouuan @ 2019-10-29 19:15:27
如果这题不改数据范围的话就是个假题...
by ouuan @ 2019-10-29 19:15:49
~~其实加个保证数据随机也行~~
by 闹闹、 @ 2019-10-29 19:16:57