网络流
网络流又名网络瘤。
流网络
流网络是一个有向图，可以表示为 \(G = (V, E)\)。
点集包含源点，汇点和中间点。
边集当中的每条边都有一个值，称为容量。
对于任意一个流网络是不考虑反向边的。
可行流
定义任意一个可行流都用 \(f\) 表示。
如果给定一个流网络每条边的流量，并且满足以下两个条件，则称 \(f\) 为可行流：
- 容量限制。
- 流量守恒。
容量限制：
对于 \(G\) 中的任意一条边都有：
\[0\le f(u, v)\le c(u, v) \]其中 \(f(u, v)\) 表示边 \((u, v)\) 的流量，\(c(u, v)\) 表示边 \((u, v)\) 的容量。
流量守恒：
\[\forall x\in \frac{V}{\{s, t\}}\ \sum_{(v, x)\in E} f(v, x) = \sum_{(x, v)\in E} f(x, v) \]定义 \(|f|\) 为源点流向汇点的流量值。
\[|f| = \sum_{(s, v)\in E} f(s, v) - \sum_{(v, s)\in E} f(v, s) \]最大流是指所以可行流中流量值最大的流。
一个流网络会有非常多个可行流。