网络流：Ford-Fulkerson 增广路算法

Ford Fulkerson 算法

对于边 $(u,v)$，我们定义 Residual Capacity $c_f(u,v)=c(u,v)-f(u,v)$。把所有剩余容量 $\gt 0$ 的边构成的子图定义为 Residual Graph $G_f$。

Residual Graph 能够 work 的核心在于对 Backward Edge 的理解。Forward Edge 上的增广和 Backward Edge 上的增广可以抵消。

退流

Ford-Fulkerson 增广算法的时间复杂度是 $O(nmf)$ 的，受容量最大的边的影响。

正确性证明