网络流总结

0. 网络流定义
   参见 \(OI\ Wiki\)。

1. 最大流算法
   定义：最大的可行流。
   思想：建出原图的残量网络，不断在残量网络上尝试进行增广，最后若没有可增广的路径则求得最大流。

一种可以求得最大流的算法：Dinic

1. 求出残量网络 \(G\) 以 \(S\) 为源点的分层图 \(L\) 。
2. 使用 DFS 算法搜索原图中的增广路径，每次从 上次经过此节点的第一条没有满流的边 \(w\in L\) （即当前弧）开始遍历。增广出的流立刻在原图上进行修改。
3. 返回第 1 步，直到 \(S\) 到 \(T\) 不连通为止。

时间复杂度：证明参见 \(OI\ Wiki\)，本人还没有搞懂。

2. 最小割
   性质：\(Flow_{max} = Cut_{min}\)