最大流

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

最大流问题

设赋权有向图 $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)$，以下命题等价：

1. $f$是$G$的最大流
2. 残余网络不存在增广路径
3. 最大流=最小割

残量网络

残量网络是一个双向图。
定义剩余容量$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算法