1. 网络流

1.1. 定义

1.1.1. 网络

网络是指一个有向图 \(G=(V,E)\)，每条边 \((u,v)\in E\) 有一个权值，\(c(u,v)\) 称为容量，当 \((u,v)\notin E\) 时，有 \(c(u,v)=0\)。

特殊地，在图中有源点、汇点两点，分别为 \(s\in V,t\in V\)。

1.1.2. 流

设流函数 \(f(u,v)\to\R(u,v\in V)\) 表示由二元组 \((u,v)\) 向实数集 \(\R\) 的映射，我们称 \(f(u,v)\) 为边 \((u,v)\) 的流量。

流函数 \(f(u,v)\) 需满足以下性质：

容量限制：对于每条边，其流量不能超过其容量，即 \(f(u,v)\le c(u,v)\)。
斜对称性：相反两边流量和为 \(0\)，即 \(f(u,v)=-f(v,u)\)。
流守恒性：从源点流出的流量等于流入汇点的流量，也可称除源汇点外所有点流入流出流量相等，即 \(\forall x\in V\land i\notin\{S,T\},\sum f(u,x)=\sum f(x,v)\)。

流函数完整定义：

\[f(u,v)=\begin{cases}f(u,v),&(u,v)\in E\\-f(v,u),&(v,u)\in E\\0,&(u,v)\notin E,(v,u)\notin E\end{cases} \]

1.1.3. 其他定义

对于当前状态下的网络，定义源点流出的流量（流入汇点的流量）为网络此状态下（当前流）的流量。

对于边 \((u,v)\) 定义 \(C_f(u,v)\) 为此边容量与流量之差，表示此边的剩余流量，即 \(C_f(u,v)=c(u,v)-f(u,v)\)。

对于图 \(G\) 定义 \(G_f\) 为 \(G\) 中所有节点与剩余流量大于 \(0\) 的边构成的子图，表示残余网络，即 \(G_f=(V,E_f)\)，其中 \(E_f=\{(u,v)|c_f(u,v)>0\}\)。

定义增广路 \(P\) 为残余网络 \(G_f\) 上从 \(s\) 到 \(t\) 的路径。

定义割，将点集 \(V\) 分为无交集的两集合 \(A,B\) 且 \(s\in A,t\in B\)，这种点的划分方式称为割。定义割的容量为 \(\sum\limits_{u\in A} \sum\limits_{v\in B}c(u,v)\)，割的流量为 \(\sum\limits_{u\in A} \sum\limits_{v\in B}f(u,v)\)。若边 \((u,v)\) 中 \(u,v\) 所属点集不同，称此边为一条割边。

1.2. 网络最大流（最小割）

进入正题，给定网络 \(G=(V,E)\) 与源汇，求此网络的最大流量。

1.2.1 最大流最小割定理

最大流等于最小割，证明如下。

对于每一单位的流量，设其经过割边 \((u,v)(u\in A,v\in B)\) 的次数为 \(\mathrm{to}\) 经过边 \((v,u)\) 的次数为 \(\mathrm{back}\)。一定有 \(\mathrm{to}=\mathrm{back}+1\)，否则不可能从源点流至汇点。

可以得出流量等于割边流量不大于割边总容量，即割的容量。得出结论：

任意一组流的流量不大于一组割的流量。

当最大流存在时，此时残余网络一定无法增广，从而得到 \(s,t\) 不连通，残余网络也不连通，自然我们得到了一组割，此时最大流量等于割的容量。得出结论：

存在一组流的流量等于一组割的容量。

综上所述，可以得到最大流等于最小割。

1.2.2. 增广

采用贪心的思想对残余网络 \(G_f\) 进行增广，具体围绕以下两原则：

能流满就流满
不断寻找增广路

具体地，对于我们在 \(G_f\) 上找到的一条增广路 \(P\)，根据能流满就流满的原则，我们令其增加流量 \(c_f(P)=\min\limits_{(u,v)\in P}c_f(u,v)\)。

为保证贪心的正确性，我们尝试加入反悔操作。将边 \((u,v)\) 的流量增加 \(c_f(P)\)，可以理解成将边 \((u,v)\) 的剩余容量减少 \(c_f(P)\)，我们在进行此操作的同时将反边 \((v,u)\) 的剩余容量减少 \(c_f(P)\)，使得我们可以在接下来的操作中进行增广。所以对于每一条边来说我们维护的实际上是其剩余流量。