最大流

总结一下最大流的各种算法

最大流问题

设赋权有向图D(V,E,C),其中每一条边的权值c∈C表示这条边的容量。流f : V * V -> R是对于边e∈E的函数,且必须满足:

f(u,v) <= c(u,v)
f(u,v) = -f(v,u)
Σf(u,*) = 0, u不是S和T

以上三个条件保证了每条边的流量|f(u,v)|(流出即为负流量)不能超过容量、流经中间节点的流量无损耗。
特别注意,对于条件2,可以得到只要有向边(u,v)上存在流f(u,v),那有向边(v,u)(该边可能不存在,这意味着c(v,u)=0)上必然存在f(v,u) = -f(u,v)。但是实际上我们只考虑流量为正的边,所以在一些教程上也只画出了这样的边。
最大流问题就是求解从源S(唯一的开始节点)能够流出的最大流量,也就是汇T(唯一的结束节点)能够得到的最大流量。

Ford Fulkerson方法

最大流最小割定理

对于网络流G(V,E),以下命题等价:

f是G的最大流
残余网络不存在增广路径
最大流的值就是这个网络的最小割。

残量网络

残量网络是一个双向图。
定义剩余容量cv(u,v)

c(u,v) - f(u,v)                 若(u,v)∈E

由cv为权的新有向图称为残量网络。并且当f(u,v)为负数时,cv(u,v)会大于c(u,v)。

增广路径

Ford Fulkerson方法的Edmonds Karp实现

与朴素Ford-Fulkerson算法不同的是Edmonds-Karp要求每次找长度最短的增广路径,即使用BFS查找增广路径。
时间复杂度是O(n*m²),空间复杂度是O(n²)。

Dinic算法

SAP算法