想当年叱诧风云左牵字符串右擎网络流，而今飘零憔悴沦落到需要学而时习之的地步

定义

对于有一个源点 \(s\) 和汇点 \(t\) 的有向图，每条边都有一个权值 \(c\) 作为容量，称这个有向图 \(G\) 是一个网络。

假设现在有 \(f\) 升水从 \(s\) 流入，而我们可以自由分配每个点的水可以朝哪个方向流出，那么显然地：

• 流出 \(t\) 的水为 \(f\) 升。
• 对于除 \(s\) 和 \(t\) 以外的所有点，流入的水量等于流出的水量。
• 对于任意一条边，流经的水量不超过容量。

对于这个网络，任选出一部分点与 \(s\) 分为一组，剩下与 \(t\) 分为一组，该操作称为「割」。一个割的「容量」定义为 \(s\) 组与 \(t\) 组间连边的容量和。

那么接下来就会由这个模型衍生出许多问题：

• 最大流问题：找到一种分配方式最大化 \(f\)。
• 最小割问题：找到一种割的方案最小化割的容量。
• 最小费用最大流问题：给每条边除容量 \(c\) 外外加一个费用权值 \(w\)，需要在保证最大化 \(f\) 的前提下最小化 \(\sum f(u, v)\times w(u, v)\)。

接下来会分别介绍解决这几种不同问题的方法。

最大流问题

一个主要的思想是 贪心寻找增广路更新当前答案。