甲醛的小屋

最近学离散发现网上对于最大流算法介绍的比较少，因此写个 blog 记录一下相关的知识点

最大流

定义一个有向图中的两个顶点分别为源点和汇点，源点入度为 0，汇点出度为 0，每条边有属性最大流量(maximum capacity)，表示该边能通过的流量的最大值。我们称该有向图从源点到汇点的最大的流量值即为该图的最大流。

对于如上图的一张图，想要获得从源点 1 到汇点 6 的最大流，我们可以使用如下的朴素算法：