想当年叱诧风云左牵字符串右擎网络流,而今飘零憔悴沦落到需要学而时习之的地步
#定义
对于有一个源点 s 和汇点 t 的有向图,每条边都有一个权值 c 作为容量,称这个有向图 G 是一个网络。
假设现在有 f 升水从 s 流入,而我们可以自由分配每个点的水可以朝哪个方向流出,那么显然地:
- 流出 t 的水为 f 升。
- 对于除 s 和 t 以外的所有点,流入的水量等于流出的水量。
- 对于任意一条边,流经的水量不超过容量。
对于这个网络,任选出一部分点与 s 分为一组,剩下与 t 分为一组,该操作称为「割」。一个割的「容量」定义为 s 组与 t 组间连边的容量和。
那么接下来就会由这个模型衍生出许多问题:
- 最大流问题:找到一种分配方式最大化 f。
- 最小割问题:找到一种割的方案最小化割的容量。
- 最小费用最大流问题:给每条边除容量 c 外外加一个费用权值 w,需要在保证最大化 f 的前提下最小化 ∑f(u,v)×w(u,v)。
接下来会分别介绍解决这几种不同问题的方法。
#最大流问题
一个主要的思想是 贪心寻找增广路更新当前答案。