0. 基本定义
一个网络 \(G=(V,E)\) 是一张有向图，\(G\) 中每条有向边 \((x,y)\in E\) 都有一个给定的权值 \(c(x,y)\)，称作边的容量。特别地，若 \((x,y)\not\in E\)，则 \(c(x,y)=0\)。\(G\) 中还有两个特殊节点 \(S,T\in V\;(S\ne T)\)，分别称为源点和汇点。
函数 \(f(x,y)\) 是定义在节点二元组 \((x\in V, y\in V)\) 上的实数函数，具有三条基本性质：
- 容量限制：\(f(x,y)\le c(x,y)\)。
- 斜对称性：\(f(x,y)=-f(y,x)\)。
- 流量守恒：\(\sum_{(u,x)\in E} f(u,x)=\sum_{(x,v)\in E} f(x,v)\)。
\(f\) 即为 \(G\) 的流函数，对于 \((x,y)\in E\)，\(f(x,y)\) 称为边的流量。\(c(x,y)-f(x,y)\) 称为边的剩余容量。\(\sum_{(S,v)\in E} f(S,v)\) 称作整个网络的流量。
1. 最大流
最大流：网络的最大流量。
1.1 EK 增广路算法
增广路：一条从源点到汇点的所有边的剩余容量 \(≥0\) 的路径。
残留网：由网络中所有结点和剩余容量大于 \(0\) 的边构成的子图，这里的边
包括有向边和其反向边。
建图时每条有向边 \((x,y)\) 都构建一条反向边 \((y,x)\)，初始容量\(c(y,x)=0\)。
构建反向边的目的是提供一个“退流管道”，一旦前面的增广路堵死可行流可以通过“退流管道”退流，提供了“后悔机制”。
算法流程：
