2024 年春节集训 _ 第四课 - 网络流

考虑 \(EK\) 算法求解最大流。

每次找一条最小剩余流量 \(d>0\) 的 \(s\rightsquigarrow t\) 的路径。然后对之流下 \(d\) 的水。这个操作我们称之为增广，所找到的这条路径叫做增广路。

一直增广到不存在任何增广路为止。

发现这样的贪心策略有时是错误的。

考虑反悔。连一条反边，反边最开始容量为 \(0\)，在每次正边流过的时候反边剩余流量增加。增广时可以考虑反边的流。但是会有很多反边的起点是没办法到达的。

所以增广依然会结束。

这样连反边然后不断增广的算法被称作 \(EK\) 算法。

最大流最小割定理

定义 \(s-t\) 割为将 \(s,t\) 不连通所要切断的边边权之和。

最大流 \(=\) 最小割。

证明略。