最大流算法复杂度分析

阅读量: searchstar 2021-11-11 23:15:44

Categories： Tags：

¶ Ford-Fulkerson算法(1956)

非常简单，直接在残量网络上dfs找到一条增广路，然后更新残差图，不断重复，直到找不到增广路。然后得到的就是最大流。

如果所有的边的容量都是0到U的整数，那显然最大流最大是nU。每次增广都至少使得总流量增加1，所以最多有nU次增广。找增广路的复杂度是，m是边数，所以总的复杂度就是。如果U是1，那总复杂度就是。

注意，如果容量可能是无理数的话，那这个算法可能永远不会停止。例子我也不会举。

¶ Capacity Scaling

为了使得找到的增广路容量尽可能大，先在只含容量大于等于的边的子图中不停找增广路，直到找不到为止。然后将减半，再重复，直到变成0。可见这个优化只在所有边的容量都是整数的情况才有用。

设U为最大的边容量，的初值设为。显然，每个scaling phase一开始的时候子图的边容量都在的范围里，所以这个scaling phase最多能够增广出的流量。由于每次增广最少能增广出的流量，所以在一次scaling phase中，增广次数为。每次找增广路的复杂度是，最多有个scaling phase，所以总复杂度是。

¶ Dinic：最短增广路

Dinic用BFS找增广路，这样每次找到的都是最短增广路。

L1. 找到的最短增广路的长度单调不减。

将最短增广路长度不变的增广称为正常增广，将长度严格单调增加的增广称为特殊增广。

L2. 最多连续m次正常增广之后必有一次特殊增广。

L3. 一组连续的正常增广消耗的总时间为O(mn)。

为了证明这些性质，先引入admissible graph的概念。设d(v)为v到t的距离，l(e)是边e的长度（通常为1），找到残差图中只含满足d(v) = d(w) + l(v, w)的边(v, w)的子图，也就是说每条边都是某个点到t的最短路上的边。在这些边里进一步筛选出在s到t的最短路上的边，这些边构成的子图就是admissible graph，记为L。

¶ L1证明

老师的证明：显然，s到t的路径中，经过admissible graph中的边的反向边的路径都比最短路径长。所以最短增广路一定是在admissible graph中的。所以最短路径的长度单调不减。

我觉得这个证明有点模糊。这里我用反证法来证明一下。

假如最短增广路的长度不是单调不减的，那么必然存在先后两条增广路a和b，使得a比b长。显然，在增广a的时候，增广路b是不存在的，否则就先找到b了。为什么增广完a之后，b就存在了呢？显然是因为b里有一些边原先是只有反向边的，然后a使用了这些反向边，然后就得到正向边了。我们假设这些反向边里，最靠近s的边是(A, B)，那么a就是由一条从s到B的路径，一条从A到t的路径，以及边(B, A)构成的。b由s到A的路径，B到t的路径，以及边(A, B)构成。我们前面说过，(B, A)是最靠近t的反向边，这就意味着在增广a的时候也存在。假设(B, A)的长度为，那么有如下表达式

得。所以，这条路径在增广a时是不存在的，这说明里至少有一条由增广a得到的反向边。假设这些反向边中离t最近的是(C, D)，由从B到C的路径，从D到t的路径，以及边(C, D)构成。显然路径在增广a的时候也存在。

假设边(D, C)在中，那么由s到D的路径，C到B的路径，以及边(D, C)构成。在增广a的时候，由于路径也存在，所以其实还可以走从s到D，再走从D到t。由于，所以这条路比a还短，矛盾。

所以(D, C)在中，那么其实又得到了一个子情况：找从B到t的增广路，先找到了更长的路径，再找到了更短的路径。不断套用上面的逻辑，会发现总是有反向边。但是里的反向边是有限的，所以假设不成立，所以最短增广路的长度总是单调不减的。

¶ L2证明

在s到t的最短路长度不变的情况下，显然每次增广产生的反向边都不会被加入到L中(L是admissible graph)，因为经过这些反向边的路径的长度都比最短路长。而且每次增广都至少消耗掉L中的一条边。由于L中最多有m条边，所以最多做m次最短增广路之后，L就被消耗完了，最短增广路长度就开始增加了。

¶ L3证明

求出admissible graph L。在L上从s开始做dfs。显然dfs到的任何一条到达t的路径都是正常增广路径，增广之后就可以至少消耗掉一条边，所以最多进行O(m)次增广（其实是L2的结论）。因为L是一个DAG，所以每次dfs都是的。所以总的复杂度是。

我们注意到，增广的时候要对路径上的每条边减去流量。这种操作其实很适合用LCT做。所以我们考虑用LCT优化之。

定义LCT的各操作如下：

make-tree(v): 让点v单独成树。
link(v, w): 把v挂到w上
cut(v, w): 让v不再是w的子节点
find-root(v): 返回v所在的树的根（用来检查两个节点是否在同一棵树里）。这个好像其实没用？因为加边的时候肯定没有环。
min-cost(v): 返回从v到root(v)的路径上的值最小的边。老师PPT上说是返回所有值最小的边的集合，我觉得这样的话复杂度可能就不是了。
update(v, x): 把x加到v到root(v)的路径上的所有边的值上。应该是用了懒惰标记。

然后维护一棵以t为根的树（让每个除了t的点都有一条出边），然后调用min-cost(s)就可以找到s到t的路径上容量最小的边(v, w)，然后调用update从这些边上减掉容量，然后调用cut把这条容量最小的边删掉。这时v成了s所在的树的根了，如果v还有出边，就直接把这条边加到LCT里，因为这条边一定是指向以t为根的树的某个节点的，因为L是一个DAG，如果v的出边指向以v为根的树的节点的话，就有环了。如果v没有出边了，就把v删掉（应该是通过把指向v的那些边都cut掉），然后会得到一个森林。同样检查这些森林的根节点还有没有出边，有的话就连上，肯定能连到另一棵树上，没有的话再删。不断重复，直到所有没有被删除的节点再次都有一条出边。然后继续调用min-cost(s)找增广路。注意由于我们这里min-cost只返回一条边，所以可能会有一些容量已经减为0的边没有被cut掉，所以min-cost可能会返回容量为0的边。这时就直接把这条边cut掉，然后继续就好了。

每轮的时间复杂度是的，然后每轮都至少会删掉一条边，所以最多m轮。总复杂度是。