分类： 网络流

网络流学习笔记——最大流

想象这样一个场面：从自来水厂到你家有若干根水管，每根水管都有一个流量上限，你想要求出到你家的水流量最大是多少。

这就是经典的网络最大流问题。

在详细介绍最大流的解法前，让我们先认识一个概念，增广路。

何谓增广路？指的就是一条从源点（水厂）到汇点（家）的一条路径，这条路径可以使流到你家的水量增加。

我们求解最大流问题，自然就是不停找增广路的过程。可以证明，如果图中没有增广路，那么当前的流就是最大流。

继续阅读网络流学习笔记——最大流