网络流（network flow）就是一个网络（有向图）上的流。
一、前置知识
1.1 割（cut）
把网络分为 $S, T$ 两部分，使得源点在 $S$ 中，汇点在 $T$ 中，其容量 $V$ 为所有从 $S$ 到 $T$ 的边的容量之和，这就是一个割。
1.2 增广路（augmenting path）
从源到汇的流（经过的边的流量的最小值）大于 $0$ 的路径。
1.3 残余网络（residual network）
在经过一些流后，剩余的流量组成的网络。
1.4 最大流最小割定理
设 $mf$ 为最大流，$mc$ 为最小割。
结论：$mf = mc$。
下面为本定理证明。
把跑完最大流（Ford-Fulkerson）剩下的残余网络，分为两部分 $S, T$，其中 $S$ 包括所有可以从源点通过非 $0$ 的边到达的点，$T$ 包含剩余的点。
首先，显然 $mf \le mc$，因为从源到汇必定会跨越 $S, T$ 两部分。
那么如何证明 $mf = mc$ 呢？
设这种割放在原图中的容量为 $c$，此时算出的最大流为 $f$。
此时，$f \ge c \ge mc$，又 $f \le mf \le mc$，所以 $mf = mc$。
值得一提的是，这也说明 $f = mf$。
二、最大流
2.1 Ford-Fulkerson 算法
考虑寻找增广路。
每找到一条流为 $f$ 的增广路，就将其经过的边的流量减少 $f$，并且答案增加 $f$。
但是！我们看下面这个图：
如果取到红色的一条增广路，那么计算出的最大流就是 $1$，但是选绿边可以做到 $2$ 的最大流。
我们希望“反悔”，把我们之前用掉的流量退回去。所以我们对于每一条边建一条反边，用来“反悔”，每次一条边减少 $f$ 时，其反边增加 $f$。
在这个新的图上找增广路，不用考虑这条边原来是否存在，直接跑就可以了。
根据上面证明最大流最小割定理的部分，可知本算法的正确性。
2.2 Edmonds-Karp 算法
就是 Ford-Fulkerson + 找增广路用广搜。
和用深搜 + 一些剪枝和避免重复访问，是一样的复杂度。
2.3 Dinic 算法
把图分层（同样只用流量不为 $0$ 的边，每条边也有反边）。
在找增广路时，每条边必须通往下一层（离源点更远的一层，在同一层也不行）。
把一个分层方案“榨干”（即找到所有增广路）时，重新分层。
在源点与汇点（通过流量不为 $0$ 的边）不连通时结束。
在上图中，橙色是分层，绿色是合法的增广路，红色是不合法的增广路（$C \to B$ 回到了上一层），
2.4 Dinic 优化
由于 Dinic 在找增广路时也是一条一条找，而从一个点延伸出的边中已经找过发现没有增广路的，以后肯定也没有了，所以可以记录下每个点上次遍历到了哪，下次遍历时继续即可。
每次重新分层时，这个记录便失效了。
三、有上下界的网络流
在这里，「可行流」指符合所有边流量上下界并且非源汇点流量平衡的流。
更加具体地说，可行流即为在边有流量最大和最小限制的网络上，满足所有边的流量限制的最小流。
3.1 无源无汇上下界可行流
假设我们有上面这个图，边上标注的是允许通过的最小和最大流量。
现在，每条边的流量取其最小值，这是它必须通过的流量。
在这个“最小图”上，对于每个点 $x$，如果入边的流量和 $i$ 大于出边之和 $o$，就建立一条边 $(S, x, i - o)$，反之则建立 $(x, T, o - i)$。
（$S$ 为超源点，$T$ 为超汇点）
然后，我们把所有原图中有的边的流量设为最大流量与最小流量之差。
最后，在这个图上跑最大流，看超源点 $S$ 是否满流即可。
这整个过程，就相当于把所有最小限制消去，变成一个相对的虚拟边（入和出重合的部分就相当于是在转圈，自动满足）。
3.2 有源有汇上下界可行流
和无源无汇的情况一样，建出超源超汇点，并且将原图所有边的流量修改。
与无源无汇的情况不同的是，原图的源点与汇点（可以转换为各一个）是不平衡的（入流量不等于出流量），因为本来就不需要（或者说要求）平衡。为了抵消它的影响，我们在原图的源汇点之间建一条边 $(t, s, +\infty)$。
然后在这个图上跑最大流，刚刚添加的那条边实际使用了的流量即为原图的可行流流量。
3.3 有源有汇上下界最大流
在算出可行流流量后，在原图的残余网络上再跑一遍最大流，将二者相加即为答案。
（实际上，这就相当于是在新图残余网络上跑一遍最大流的结果，因为只多了一条不会影响结果的边）
3.4 有源有汇上下界最小流
在算出可行流流量 $f_1$ 后，删掉新添加的边 $(t, s, +\infty)$（当然也要删反边，但是不删也没影响），计算 $t \to s$ 最大流 $f_2$，答案为 $f_1 - f_2$。
（实际上，就是先满足每条边的最小条件，再减掉可以流回去的）
四、最小费用最大流
每条边有一个「费用」，表示通过一个单位的流需要的代价。求最大流以及达到最大流所需的最小代价。
4.1 SSP (Successive Shortest Path) 算法
我们之前找增广路的方法是直接搜，并没有考虑这个问题，要解决它我们只需要在找增广路的时候找费用最小的就可以了。可以直接跑最短路，因为费用会叠加。
SSP 算法在原先最大流算法的基础上，将寻找增广路的方式改为了最短路算法。