网络流

网络流是图论中一个博大精深的分支。

一个网络Ｇ＝（Ｖ，Ｅ）是一张有向图，途中每条有向边（ｘ，ｙ）属于Ｅ，都有一个给定的权值ｃ（ｘ，ｙ），称为边的容量。特别地，若（ｘ，ｙ）不属于Ｅ，则（ｃ，ｘ）＝０。称为边的容量途中还有两个指定的特殊节点Ｓ属于Ｖ和Ｔ属于Ｖ（Ｓ不等于Ｔ），分别称为原点和汇点。

设ｆ（ｘ，ｙ）是定义在二元组（ｘ属于V，ｙ属于Ｖ）上的实数函数，且满足：

１．边的流量小于边的容量。ｆ（ｘ，ｙ）＜ｃ（ｘ，ｙ）

２.ｘ到ｙ的流量和ｙ到ｘ的流量是相反数。ｆ（ｘ，ｙ）＝－ｆ（ｙ，ｘ）

３.ｘ的流入量和流出量是相等的。

ｆ称为网络流的流函数。ｆ（ｘ，ｙ）称为边的流量，ｃ（ｘ，ｙ）－ｆ（ｘ，ｙ）是边的剩余流量。

所有与Ｓ－＞ｖ的ｆ（ｓ，ｖ）之和是整个网络的流量。

图中每条边的反向边其实都有一个负的流量。

流量守恒定律告诉我们网络中除了原点和汇点以外，每个点的流入量和流出量是一样的。

最大流

对于一个给定的网络，合法的流函数有很多，其中使从Ｓ流出的流最大的流函数，被称为网络流的最大流，此时的流量被称为最大流量。

对于二分图的最大匹配问题，我们可以新增加一个原点和汇点，左部点连接Ｓ，右步点连接Ｔ，网络中每条边的容量都是１。二分图的最大匹配数就是网络的最大流量。

流过的边和点就是匹配边和匹配点。

另外的，如果要求二分图的多重匹配，改变一下边的容量就可以了。

（Ｓ连接左部点的边的容量，Ｔ连接右部点的边的容量，左部点和右部点的边的容量是１）

Ｅｄｍｏｎｄｓ－Ｋａｒｐ增广路算法

增广路定义：一条从源点Ｓ到汇点Ｔ的各条边的剩余容量都大于０的路径。

可以让一股流沿着增广路到达T，使得网络的流量增大。

Ｅｄｍｏｎｄｓ－ｋａｒｐｓ的思想就是不断用ＢＦＳ寻找一条增广路，直到网络上不再存在增广路为止。

该算法在寻找增广路的过程中只考虑ｆ（ｘ，ｙ）＜ｃ（ｘ，ｙ）的所有边，用ＢＦＳ找到一条从Ｓ到Ｔ包含边数最小的路径，同时计算出该路径上的所有边中剩余容量的最小值ｍｉｎｆ，则整个网络的流量就可以增加ｍｉｎｆ。

值得注意的是一条边的反向边的容量是负数。

在存储图的时候，把网络中的有向边和反向边存在相邻的位置，这样会方便查询，例如ａ在（２），ａ‘在（３），ｂ在（４），ｂ’在（５）

这样所有的正向边都在下标为偶数的邻接表中，所有反向边都在下标为奇数的邻接表中。

当一条边流过（ｘ，ｙ）时，剩余容量减少ｅ，（ｙ，ｘ）的剩余容量增加ｅ

（反向边的存在其实就是为了提供反悔的机会，如果我们的正向边的容量减少了１，就代表有流量１流出了该边，如果不存在反向边，也就是一定让流从这个点流出去１个，可能会导致有一些更加优秀的也需要从这个点流出去的流没有办法流出去。所以我们提供一个返回的机会，让原来的那个流按照接下来的这个流流动的方式流到Ｔ（也不一定是全部，可能只是之前的一些流量，相当于分流），而现在的流相当于采用了原来的流的路径（路径是采用了，但是流量可能不一样，可能是代替了原来流的其中一部分流量，而原来流的这一部分采用了一种（也就是现在新找的）新的流出方式））。

反向边是个好东西（但对于**不好的我来说，可能有点抽象）

时间复杂度O（ｍ^２ｎ），一般能处理１ｅ３～１ｅ４的网络））））有点玄学）

Ｄｉｎｉｃ算法

残留网络：在任意时刻，网络中所有的节点以及剩余容量大于０的边所构成的子图。

Ｅｄｍｏｎｄｓ－Ｋａｒｐ算法每轮可能会遍历整个残留网络，但只找出了一条增广路，进步空间大大的大（想起了某国ｐｅｒｏｎ）！

节点的层次ｄ［ｘ］：从Ｓ到ｘ最少需要经过的边数。

在残留网络中，满足ｄ［ｙ］＝ｄ［ｘ］＋１的边（ｘ，ｙ）构成的子图被称为分层图。

该分层图是一张有向无环图。（这跟原图有没有环没有关系）

步骤：（ｃｙｃｌｅ）

１．在残留网络上ＢＦＳ求出节点的层次，构造分层图。

具体地：从Ｓ开始，不断向外扩展。顺便可以加上当前弧优化：我们建立好了一张分层图以后，就不断一条一条有方向性的寻找增广路。但是从有一些边走注定不能找到增广路，再走一遍没有意义，所以记录一下，下次跳过这些边。

２.在ＤＦＳ寻找增广路，在回溯时更新剩余容量。

时间复杂度Ｏ（ｎ^２ｍ）一般能处理１ｅ４～１ｅ５规模的网络。