网络流

网络流是一张模拟运输或流动的图。其边的权重代表边的容量。一般我们将其看做一个水流系统。有一个源节点和一个汇点（流出点）。每一条边上的流量不能超过容量，而每一个节点也不能存储任何水量。另外，这张图不存在自循环，且不存在反平行边(一对边(u,v)与(v,u))。

而对于任意一个节点，流入量等于流出量。

如果遇到反平行边，可以将其中一条边中加入一个新的节点来避免反平行边。

而若是有多个源节点和多个汇点，则可以建一个超级源节点和超级汇点，其分别指向源节点和被汇点指向，边权为无限即可。

Ford-Fulkerson

一个流是一个从源节点到汇点的一条路径。并且这条路径有一个大小，也就是水流的大小，水流的大小必须小于路径上最小的容量。

残存网络

对于一个网络流，它所有的边都是单向的。我们将其补全为双向的，顺其方向的路径上的权重表示这条路径上流的大小，而逆其方向的路径(不存在于网络流中的)权重表示这条路径上还能通过的流的大小，也就是容量减去流的大小。

这样形成的图被称为残存网络。

增广路径

残存网络中的一个流就是原网络流中的一个增加流。

$(f↑f')(u,v)=f(u,v)+f'(u,v)-f'(v,u)$，因为残存网络中的逆向流就是减少流，正向流就是增加流。

另外，由于该流是在残存网络中的一个流，所以最终肯定是汇入汇点的，因此汇点的流量大小是增加的，这样的流被称为增广路径。

只要不断地在残存网络中找这样的增广路径并将其增加到原网络流中，汇点的流就是不断增加的，直到找不到这样的增广路径，此时就是最大流了。

最小割

一个割就是将所有的节点分为两个部分，源节点和汇点必须属于任意一个部分。

假设源节点所在的部分为S，汇点所在的部分为T。净流量的大小就等于S→T的流量减去T→S的流量。由于流量在路上是没有损失的，也就是说S和T的内部流量都是这么多，因此净流量的大小对于任何割都是一样的(这很显然)。因此净流量的大小就是网络流中流的大小。

我们假定对于一个割来说，它的容量为S→T的容量和，因此它肯定是大于割的净流量的，因为净流量<S→T的流量<S→T的容量和，因此最大流的大小受最小割的容量限制，也就是最大流的值等于最小割的容量。

这一点与不存在增广路径是等价的。这一点对于线性规划来解网络流非常关键。

实现

一般使用深搜的方法来寻找增广路径，因为只需要找到任意一个路径就可以了。不断寻找并更新网络流和残存网络，直到增广路径不存在。

由于每次增广路径为整体流的贡献至少为一个单位，因此整体增广路径的次数为$O(|f^*|)$，$f^*$为最大流。而每一次寻找增广路径并更新的复杂度为$O(E)$，总体的复杂度就是$O(E|f^*|)$，这复杂度非常玄学。

Edmonds-Karp

选择增广路径选择从源节点到汇点的最短路，这里的最短路是指假设所有的边的权重都为1的情况下。

可以证明源节点到任意节点的最短路径必然是随着操作的进行而单调递增的(算法导论引理26.7，证明没懂）。

我们称一条边为关键边当且仅当这条边在增广路径上且容量最小。

如果流量增加了一次，那么必然至少有一条边成为了关键边。因此流量增加次数小于等于所有边成为关键边的次数。

当我们假设一条边成为了关键边，那么它残存网络上这条边就会成为0。如果希望它第二次成为关键边，那么反向边必须已经在增广路径上出现过一次。因为只有这样它的权重才不会为0了。

由上述的引理26.7可知，每个循环所有节点的最短路径都不会减小。另外，假设某一条路径是源节点到汇点的最短路，那么这条路径也必然是源节点到这个节点的最短路，假设某条关键边的两边节点分别为u和v，那么第一次成为关键边时$\delta(u)+1=\delta(v)$，而为了保证它第二次成为关键边，那么，在反向路出现在增广路径中时$\delta'(v)+1=\delta'(u)$，而$\delta(v)'\ge\delta(v)$，因此一次成为关键边u的最短路至少增加2，但最短路径必然是少于整体节点数的（最短路径对于每一个节点最多经过一次），因此一条边最多进行节点数/2个循环。而总共有E条边，因此最多总共$O(VE)$次循环。总体就是$O(VE^2)$。