关于常见费用流算法的复杂度和本题数据范围以及多项式复杂度费用流算法

回复帖子

@ouuan 2019-10-29 18:59 回复

常见费用流算法(把 Dinic 的 BFS 改成求最短路)复杂度上界是 $O(nmf)$,其中 $f$ 是最大流。

Zadeh 在 论文 中给出了 hack 方法,在 Min_25 的博客 中给出了数据生成器。点数为 $42$ 时生成出的数据:传送门

本题首先数据范围不全,没有给出容量和费用的范围。

其次,要想让常见费用流算法保证通过,应当设置较小的流量,如保证 $1\le n, m\le 100$, $w_i\le 500$。我个人只了解上面提到的那种 hack 方法,因此如果不保证流量(或者说保证在 $10^9$ 以内),只保证 $1\le n\le 30$,我也不清楚是否能够 hack。

然后是我写的博客 基于 Capacity Scaling 的弱多项式复杂度最小费用流算法。它的复杂度是 $O(m^2\log U\log m)$,在本题只能得到 $73$ 分,所以也不发题解了(

最后,如果只是想要在 OI 中解决费用流问题,掌握常见的那种费用流算法就够了,因为一般的题都有特殊性质(图的形态 / 流量上限),没法卡。如果是出费用流题,设置数据范围时需要留意是否能够保证标程通过。像本道模板题就是个反例。

虽然在博客里说过了,还是再提醒一遍:

尽管多数人使用的 SSP 算法是伪多项式复杂度的,我并不建议在题目中卡掉它。

但需要注意的是,“不卡掉”是指设置合适的数据范围,使得 SSP 可以确保通过。如果设置了不合理的数据范围而测试数据中没有卡掉 SSP,那么不仅卡了 SSP,数据也不合格。

(好像常见费用流算法复杂度不对这事很多人都知道..就当是再宣传一下博客吧..)

我当然是没有期望洛谷管理会来改本题数据范围的

@ouuan 2019-10-29 19:00 回复 举报

应该是 "Min_25 在博客中给出了数据生成器" /fad

@yurzhang  ATRI 2019-10-29 19:01 回复 举报

这个支持,每次看见数据范围几万几十万正解网络流的题我都想骂出题人

@yurzhang  ATRI 2019-10-29 19:03 回复 举报

@ouuan 还有,边有单位容量的图跑 Dinic 复杂度好像会低,也就是平常讲的 $O(n^2m)$ 其实并不是下界

@BadWaperZ 2019-10-29 19:05 回复 举报

没看很懂lz啥意思啊QAQ,是指Dinic跑最短路是错的,然后EK时间复杂度不对吗

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。