网络流的核心在于建图。建图建出来之后，剩下的基本上只是模板了。
1 基本定义
一个网络是一张有向图 \((V, E)\)，其中每条边都有一个流量 \(c(u,v)\)。一个网络有一个源点 \(S\) 和一个汇点 \(T\)。
网络流满足以下几条性质：
-
流函数 \(f : (x, y) \rightarrow \text{R}\) 是一个二维数对到实数域上的一个映射。
-
容量限制：\(f(x, y) \leq c(x, y)\)。
-
斜对称：\(f(x, y) = -f(y, x)\)。
-
流量守恒：\(\forall i \neq S, i \neq T, \sum f(u, i) = \sum f(i, v)\)。
以下是网络流的相关定义。
-
对于有源汇网格，\(\sum f(S, v) = \sum f(u, T)\)，也就是初始流量和结束流量相等。
-
残量网络 \(G_f = (V, E_f)\)：\(c(u, v)_f = c(u, v) - f(u, v)\)，若 \(c(u, v)_f = 0\)，则视为 \((u, v) \not \in E_f\)。
-
增广路：残量网络 \(G_f\) 上的一条从 \(S\) 到 \(T\) 的一条路径。
-
割：将点集划分成 \(A, B\)，则称这个划分为一个割。这个割的权值为 \(\sum_{u \in A, v \in B} f(u,v)\)。若 \(u \in A, v \in B\)，则称 \((A, B)\) 为割边。
2 网络最大流
最著名的网络最大流算法有 Dinic 和 Edmonds_Karp。其他我不会，不过多介绍。
2.1 增广
2.2 Edmonds_Karp
2.2.1 EK 算法简介
2.2.2 EK 代码实现
2.2.3 EK 复杂度分析
2.3 Dinic
2.3.1 Dinic 算法流程
2.3.2 Dinic 注意细节
2.3.3 Dinic 代码实现
什么？你问我没有 Dinic 复杂度证明？我不会啊！
3 网络最小割
最小割是一个网络 \(G\) 中权值最小的一个割。
3.1 最大流最小割定理
一个网络的最大流等于其最小割。
证明待补。
4 网络流 24 题
makabaka.