总结一下最大流的各种算法
最大流问题
设赋权有向图 $D(V,E,C)$，其中每一条边的权值$c \in C$表示这条边的容量。流$f: V * V \rightarrow R$是对于边$e \in E$的函数。我们定义唯一的开始节点$S$是源，只发出流量；唯一的结束节点$T$是汇，只接受流量。一个流网络具有以下的形式
- 流入流量取正号，流出流量取负号
- 每条边的流量$|f(u,v)|$不能超过容量
- 流经中间节点的流量无损耗
形式化的表述如下
$$
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)$。
