网络流

网络流 (network-flows) 是一种类比水流的解决问题方法，与线性规划密切相关。图论中的一种理论与方法，研究网络上的一类最优化问题。
网络流的图可以抽象成以下模型。

对于一张边权图，每条边的权值指流量。流量 是指允许通过该边的最大权，而可以有不限多的权同时停留在一点上。

特别地，一图中存在两特殊点：源点和汇点。
源点 指初状态拥有无穷多权的点。一般题目不提供这个点（告诉你就等于告诉你是网络流了），它是一个虚点。
汇点 指出度为 $0$0 的、用于记录答案的虚点。
如上图所示，$ST$ST 是源点，$ED$ED 是汇点。

求从源点通过边走到汇点的权的最大值。这就是 最大流 问题。你可以把它想象成：有一些水管，它们有一定的耐久度，流过一定量的水后就会断裂失效。从一个有无穷多水的点开始流，最多有多少水流到汇点。

使用 Dinic 算法求最大流步骤如下。

1. 把源点视为第一层，尝试遍历所有点并求出深度；
2. 尝试 从浅到深 的顺序 从源点开始 流；
3. 重复 1. 2. 操作。若无法搜到汇点，结束算法。

例题

求下图的最大流。
其中 $\inf$inf 表示无穷大。

我们首先从 $ST$ST 分别流 $\inf$inf 到 $1,2,3$1,2,3。尝试 $1\to5,6;\ 5,6\to ED$1→5,6; 5,6→ED，对答案贡献为 $2$2；$2\to5,t\to ED,ans+5$2→5,t→ED,ans+5；$3\to4,4\to ED,ans+1$3→4,4→ED,ans+1。
所以最大流为 $2+5+1=8$2+5+1=8。

当题目描述与“流水”无关时，尝试将题目转换成流水模型。

网络流 24 题索引