学艺不精啊
增广路
- 基于一条这样的事实：S到T的最大流可以通过在残量网络中不断寻找增广路，直至不存在增广路，则当前流即可最大流。
最大流最小割定理
- 最小割：将源点S和汇点T分别在两个集合。
- 证明：一个感性的理解是，若不割掉最大流，即存在S到T的流量，故最大流=最小割
- 增广路算法结束时，已经标号a[i]的即可即为S，其他节点即为T=V-S
Dinic算法
Dinic算法通过BFS不断构造分层图，DFS寻找增广路，实现最大流。
优化
- 当前弧优化：每次dfs寻找增广路，是从上次考虑的弧开始增广，这样既可以保证不会重复访问已经满载的弧，也保证了算法的正确性。
- 炸点优化：到达源点及时返回。
模板
github