目前连 多项式复杂度的费用流算法 都没有提出吧……
好像有一个 $O(nm\log\log f)$ 的弱多项式算法？不太清楚
by WYXkk @ 2020-04-18 23:31:28
@[WYXkk](/user/130151)
Capacity scaling algorithm $O((m \log U)(m + n \log n))$
Cost scaling algorithm $O(n^3\log(nC))$
Double scaling algorithm $O(nm \log U \log(nC))$
Minimum mean cycle-canceling algorithm $O(n^2m^3 \log n)$
Repeated capacity scaling algorithm $O((m^2 \log n)(m + n \log n))$
Enhanced capacity scaling algorithm $O((m \log n)(m + n \log n))$
书上给出了这些算法。。不知道算多项式复杂度吗
by hly1204 @ 2020-04-18 23:36:51
@[hly1204](/user/242973) 后3个应该都是，但我不太清楚……我记得好像是没有的，可能我记错了
by WYXkk @ 2020-04-18 23:38:50
前面的 U 和 C 我不知道什么意思 /kk
by WYXkk @ 2020-04-18 23:39:22
不用，很多费用流题数据范围超过1000的，用多项式的反而常数过大T掉
正常出题人出费用流题大概数据是随机的（除非可以用KM做）
by panyf @ 2020-04-18 23:41:20
@[WYXkk](/user/130151)
$\log U$ (the log of the largest supply/demand
or arc capacity), and $\log C$ (the log of the largest cost coefficient)
by hly1204 @ 2020-04-18 23:41:47
比如P2053，点数600左右，边数几万，多项式的算法根本过不去
by panyf @ 2020-04-18 23:43:28
@[AK新手村](/user/221955) 这么可怕吗（
by hly1204 @ 2020-04-18 23:44:08
@[AK新手村](/user/221955) 谢谢，稍微明白了
by hly1204 @ 2020-04-18 23:44:30
@[AK新手村](/user/221955) 真就还水洛谷呗
by _sys @ 2020-04-19 01:14:16