最近在学网络流，我真是受够了网上一片一片的毫无营养的比作水流的讲解。有点不尊重的说，我觉得教材和网上的解释完全没有为我这样的初学者点明网络流到底是一个什么东西，所以，我们这些蒟蒻只能自救了……这篇文章先说基本概念，下一篇文章再说模板。

    首先，我们先要明确，网络流是一个关于图论的思想。它是一种思想因此可以解决一系列问题。但它根本上是一个关于图论的思想。要用网络流解题先要有图，OK？这是网络流里有“网络”的原因。

    然后，为什么网络流里有个“流”呢？因为网络流这个概念（或者说模型？）它的性质和水流有许多相似之处。

    我们先要有一个源点s和一个汇点t。这个源点和汇点，大部分时候是你自己建立的，偶尔题目给你图了，那时候有一定几率题目给了你源点和汇点。

    然后我们就有了一个图。例如：

    这个时候我想先介绍基本概念，具体操作我会在后面的文章中说一下。老实说，教材上光给概念的行为真是令人恼火啊……

    我们有了流量图之后，就可以给边赋值了。这个值代表什么呢？看题目而定。因为根本没有一个通解可以概括这里边权值的作用。我们要注意的是，这里的边权，只是一个理论值，是我们可以走的，而不是我们走的。我们到底怎么走，需要后面程序的计算。

    在说明网络流的三大性质之前，我们先要明确，我们的“走法”，或者叫“流”包括一系列路径。这些路径都从源点s出发，到达汇点并把它们的值加在汇点t上，汇点就是我们要求的东西。比如最大的人数，最小的花费等等。

    以上是为了帮助理解的，下面就是真的了。

    网络流有三个性质和三个重要概念。下面一一介绍。

    性质1：容量限制。也就是说我们的“走法”不能超过边权。比如一个人走过去你不能加二。

    性质2：反对称性。对于一个节点，一个人走过去和负一个人走过来等价。

    性质3：流守恒性。除了源点和汇点之外其余的节点都是用来过渡的，这个点上的流入量加流出量应当是0。

    概念1：残留网络。我们之前提到了“走法”不能超过边权。也就是说我们可能会有剩余。这个剩余是以后提升的空间。我们通常用节点来记录残余。

    概念2：增广路径。假设在“走法”之外（或之中）我们选择了一条路径。这条路径是由节点和边构成的。我们高兴的发现这条路径上的点中有的点的残余不是0。等等，有的不是0是什么意思？这里我们需要注意，我们在意的是路径中所有点的残余的最小值（这些点当然不包括源点和汇点）。这一点的理由显然，我们要在整条路径上加上一个值，我们在意的是剩余最小的边能否容纳这个值。再此基础上希望这个值最大，那么我们就要选择路径中残余量的最小值。

    概念3：割。我们可以近似的认为割就是一种分配方式。我们把网络分成两个集合。这两个集合由许多边连接。如果我们去掉割集中的边，就无法从一个集合走到另一个集合。割集中边的权值和称为割的容量。割集有很多个，其中容量最小的割称为最小割。

    这篇文章就到这里，后面我会写一些相关的模板。