关于费用流

ningago @ 2022-03-21 18:01:37

by 约瑟夫用脑玩 @ 2022-03-21 18:08:42

因为好写，而且一般人都是学了这个就用这个。

by rxjdasiwzl @ 2022-03-21 18:27:43

@ningago 因为 dinic 不能跑费用流

by moao @ 2022-03-21 18:29:32

@rxjdasiwzl ?

by rxjdasiwzl @ 2022-03-21 18:29:48

你说的大概是多路增广的费用流，但是时间复杂度不变。另外我不知道你怎么卡的费用流。

by rxjdasiwzl @ 2022-03-21 18:37:44

实测是效率差不多

by ningago @ 2022-03-21 18:55:23

@rxjdasiwzl

dinic可以啊，我一直用着呢，Ek O(nm^2)，dinic最坏 O(n^2m)，稠密图EK就寄了啊

by rxjdasiwzl @ 2022-03-21 19:26:47

@ningago 你说的复杂度都是最大流复杂度不是费用流复杂度。。。

by ningago @ 2022-03-21 19:28:34

@rxjdasiwzl

（我太蒻了竟然以为复杂度一样

by rxjdasiwzl @ 2022-03-21 19:32:45

而且基于贪心找增广路的费用流算法统称 SSP 算法，所谓 EK 和 Dinic 费用流只是单路增广和多路增广的区别，或者说 EK/Dinic 的 BFS 改成最短路，Dinic 本身只能用来做最大流。说到底是定义的问题。。。

但是这两个写法跑费用流复杂度是一样的

by rxjdasiwzl @ 2022-03-21 19:36:10

@ningago 费用流复杂度大概是用 O(nmf) 来表示的，所以增广方式只影响常数？有区别的方法是原始对偶用 Dijkstra 跑最短路，这样是 O((n+m)\log m\times f) 的，我只在流量为 2 的题目里面遇到这种方式卡 SPFA 的题目。一般情况都是 SPFA 比原始对偶的 Dijkstra 快。