最大流

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

最大流问题

设赋权有向图 $D(V,E,C)$,其中每一条边的权值$c \in C$表示这条边的容量。流$f: V * V \rightarrow R$是对于边$e \in E$的函数。我们定义唯一的开始节点$S$是源,只发出流量;唯一的结束节点$T$是汇,只接受流量。一个流网络具有以下的形式

  1. 流入流量取正号,流出流量取负号
  2. 每条边的流量$|f(u,v)|$不能超过容量
  3. 流经中间节点的流量无损耗

形式化的表述如下
$$
f(u, v) = -f(v,u) \\
f(u, v) \le c(u,v) \\
Σf(u, *) = 0, u \notin \{S, T\} \\
$$

特别注意对于条件1,可以得到只要有向边$(u,v)$上存在流$f(u,v)$,那有向边$(v,u)$上必然存在$f(v,u) = -f(u,v)$。特别地该边不存在的情况可以表示成$c(v,u)=0$,但是实际上我们只考虑流量为正的边,所以在一些教程上也只画出了这样的边。
最大流问题就是求解通过流网络从源$S$能够流出的最大流量,也就是汇$T$能够得到的最大流量。

Ford Fulkerson方法

最大流最小割定理

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

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

残量网络

残量网络是一个双向图。
定义剩余容量$cv(u,v)$
$$
c(u,v) - f(u,v) \qquad 若(u,v) \in E
$$
由cv为权的新有向图称为残量网络。并且当$f(u,v)$为负数时,$cv(u,v)$会大于$c(u,v)$。

增广路径

Ford Fulkerson方法的Edmonds Karp实现

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

Dinic算法

SAP算法