MaxFlow网络流
1 网络流基础概念
source：源点
sink：终点
Flow：流量
capacity：容量
Residual：残量
Residual Network：残量网络
Augmenting path：增广路径，表示从源点 s 到终点 t 不包含环的路径
Bottleneck capacity：瓶颈容量
2 最大流
2.1 基础概念
2.2 增广路算法
当残量网络不包含增广路径时能求得最大流
2.2.1 最大流贪心算法
最大流贪心算法只能实现局部最优，无法实现全局最优！
2.2.2 Ford-Fulkerson
-
Worst-Case Iteration Complexity
每次迭代至少增加 1 的流量，所以迭代次数 ≤ 最大流量
总结：最坏情况，迭代次数 = 最大流量。 假设有 m 条边，寻找一条增广路径的时间为 O(m)，最大流量为 f，那么最坏情况下的时间复杂度为 O(f * m) -
循环结束条件为，找不到增广路径：
- 寻找一条增广路径（augmenting path）
- 找到这条增光路径上的瓶颈容量（bottleneck capacity）
- 更新残余网络
- 添加反向边
2.3 Capacity-scaling algorithm
Ford–Fulkerson 的指数时间来源于对增广路径的选择，如下形式的选择，就只能每次增加 1 的流量，导致算法朝着指数的时间增长。
思考： 是否可以做出改变，每次选择更大的 bottleneck capacity？这样就可以有更少的迭代次数！ （即选择最少的边，最大的瓶颈容量，Capacity-scaling algorithm 诞生）
3 最小割
3.1 基础概念
3.2 最小割
3.3 最小割案例
4 流与割
4.1 基础概念
4.2 最大流求解最小割
- 通过最大流算法获得最终残余网络
- 寻找最小割（S，T）
- S ← 在剩余网络中，寻找 s 能够到底的所有点
- T ← 除开 S 中包含的其他点。
5 剩余网络
