用最通俗的语言让你学会网络流

在网上找了很久资料，虽然讲解网络流的资料很多但是浅显易懂的很少（可能是我太蒻了吧），写这篇文章只希望点进来的人都能学会网络流（都能点赞）

我尽量用通俗易懂的语言讲解，同时结合图示理解。

我将讲解以下网络流算法：

1、最大流

2、最小费用最大流

先从最基础的最大流开始：

何为最大流问题？

简单来说就是水流从一个源点s通过很多路径，经过很多点，到达汇点t，问你最多能有多少水能够到达t点。

结合图示理解：

从s到t经过若干个点，若干条边，每一条边的水流都不能超过边权值（可以小于等于但不能大于），所以该图的最大流就是10+22+45=77。

如果你还是不能理解，我们就换一种说法，假设s城有inf个人想去t城，但是从s到t要经过一些城市才能到达，（以上图为例）其中s到3城的火车票还剩10张，3到t的火车票还剩15张，其他路以此类推，问最终最多能有多少人能到达t城？（假设这个地区只有火车，没有汽车飞机，步行和骑自行车会累死就不考虑了，再假设所有人都买得起火车票。）

那怎么么解决这个问题呢？

对于这个问题，刚看到时，你有什么想法？

或许你会有一个这样的思路：从s开始找所有能到达t的路径，然后找每条路径上权值最小的边（或者说能承受水流最小的管子），再进行其它操作，就能找到这张图的最大流。

然后我们有

EK（Edmond—Karp）算法。

其实还有其它算法，但由于过于复杂（作者太懒不想画图），（以作者的语文水平）很难讲的通俗易懂，就不献丑了。

这里我就不介绍那么多公式定理之类的了（为了通俗易懂，并且不把你绕晕），为方便讲解，引入一个概念：

增广路：

增广路是指从s到t的一条路，流过这条路，使得当前的流（可以到达t的人）可以增加。

那么求最大流问题可以转换为不断求解增广路的问题，并且，显然当图中不存在增广路时就达到了最大流。

具体怎么操作呢？

其实很简单，直接从s到t广搜即可，从s开始不断向外广搜，通过权值大于0的边（因为后面会减边权值，所以可能存在边权为0的边），直到找到t为止，然后找到该路径上边权最小的边，记为mi，然后最大流加mi，然后把该路径上的每一条边的边权减去mi，直到找不到一条增广路（从s到t的一条路径）为止。（为什么要用mi呢？你要争取在这条路上多走更多人，但又不能让人停在某个城市）

具体操作：

找增广路：

那个pre数组是由来记录路径的，它长这样：

structPre{

intv;//该点的前一个点（从起点过来）

intedge;//与该点相连的边（靠近起点的）

}pre[101010];

然后直接累加最大流（注意加的时候要把改边边权减去相应的流量，防止一直重复加同一段流）

那代码是长这样的吗?

当然不是，万一第一次流错了使得这样的流法无法得到最大流怎么办？

还是以刚才那张图为例，为了防止你再翻上去，我直接再放一次：

如果你第一次的增广路是：s->3->5->t流量显然是10，第二次的增广路是s->4->5->t流量显然是35（因为5->t的流量有10点被3号点来的人占领了)。

而这种方案显然不如：s->4->5->t流量为45，s->3->t流量为10。

那程序怎么知道哪种方案最优？

它当然不知道，我们要把所有情况都找一遍，难道要回溯？

当然不，这里使用一种高级技巧，加反向边。什么意思？

以下图为例：

这是刚才那张图，我们在每条边都加了一条反向的，权值为0的边（红色的边）。

有什么用呢？

占空间？拖时间？显然不是。

先不管有什么用，加了反向边，我们再跑一次EK，这次，除了要给增广路上的边都减去该路上的最小流量以外，还要给反向边加上最小流量。为什么？先别管。

先找增广路，比如说我们走了s->3->5->t，那么图会变成：

再找一次增广路，这次比如说我们走s->4->5->t。

（那个65被洛谷打了水印我也没办法，将就看吧）

再找一次增广路，这次我们找s->4->5->3->t

好像有点奇怪。你可能会想：为什么这次搜索的时候走了反向边（红色）的边，为什么走了反向边（红色）的边会加正向边（黑色）的边？

这就好像是45个人沿着s->4->5->t的路线想去t城，到了5城却发现有10个来自3城的人先定了5->t的票！他们十分焦急，总不能让他们在5城等吧。

怎么办呢？他们通过反向边上的标记发现了那10个人是来自3城的，利用标记，他们发现那10个人可以直接从3城到t城，于是他们（利用了哆啦A梦的时光机）告诉还在3城时的那10个人可以直接走3->t这条路，然后他们就可以买到空出来的5->t的10张票了。

现在你知道反向边的作用了吧：留下一个标记，让后面的人有机会让前面的人走另一条路。

理解了反向边的作用，恭喜你已经理解了EK求解最大流算法的原理了。

下面讲解关于反向边在代码中的实现：

关于反向边在加正向边时要一起加上，边权为0，然后在寻找增广路时就没必要关注一条边是正向边还是反向边了，在统计最大流时，要把每一条经过的边的边权减去这条增广路的流（最小流量），每条经过的边的反向边（反向边的反向边是正向边，负负得正）加上这条增广路的流。

现在还有一个小问题，怎么通过一条边的编号求它的反向边的编号。

由于正向边和反向边是一起加的，所以反向边的编号与正向边的编号只相差1。

那就好办了。

如果第一条边的编号是偶数，就有

正向边的编号^1==反向边的编号；反向边的编号^1==正向边的编号。（？为什么？）

那么接下来就来证明：当正向边的编号为2n时反向边的编号为2n+1。设n的二进制表示为XXXXX，则2n==n<<1 因此2n的二进制表示:XXXXX0,而2*n+1的二进制表示：XXXXX1。

那肯定（2n）^1==2n+1;(2n+1）^1==2n。

都讲完了，那就附上完整代码：

题目是：P3376 【模板】网络最大流

还有一道模版题P2740 [USACO4.2]草地排水Drainage Ditches（水双倍经验）

那么这个（乱七八糟的）算法有什么用呢？

经典应用：二分图匹配

什么意思？

给两个集合：A，B，其中A有一些元素a1,a2,a3……，B有一些元素b1,b2,b3……

其中a1想和b1，b4，……中的一个配对，a2想和b1，b250，b2500……（这些数字没什么特别含义）配对，为最优情况下能有多少组配对成功。

二分匹配模板题：P2756 飞行员配对方案问题

怎么做呢？

其实二分匹配问题可以转换为网络流问题。

把集合A当成起点，集合B当成终点，若集合一中元素a可以对应集合二中元素b，则加一条a指向b流量为一的边

新增加两个点，s和t，s有指向所有起点的边，所有终点有指向t的边，只需计算s到t的最大流，用EK算法即可。

本题要求记录配对方案，只需在找增广路时加个标记即可。

附上代码：

其实相比于网络流，二分匹配还有更快的方法，匈牙利算法，这里就不详细讲解了，今天的重点是网络流。

对于这道题，网络流会超时，匈牙利算法不会超时：

P3386 【模板】二分图匹配

感兴趣的可以自行研究，还是给出代码吧：

其实相比于网络流，二分匹配还有更快的方法，匈牙利算法，这里就不详细讲解了，今天的重点是网络流。

对于这道题，网络流会超时，匈牙利算法不会超时：

P3386 【模板】二分图匹配

感兴趣的可以自行研究，还是给出代码吧：

然后就是最小费用最大流了

听名字就和上面讲的差不多。

什么是最小费用最大流呢？

以下图为例

上图中没打（）的为边权（最大流量），打（）的为单位流量的价格

还是用刚才那种通俗易懂的解释方法

假设s城有inf个（穷）人想去t城，但是从s到t要经过一些城市才能到达，其中s到3城的火车票还剩10张票价为6元/人，3到t的火车票还剩15张票价为7元/人，其他路以此类推，问最终最多能有多少人能到达t城？

（由于是穷人）他们希望能在最多人到达t城的同时花最少的钱，问最少的钱是多少？

有了刚才学习最大流的基础，相信接下来的讲解应该很容易看懂。

还是找增广路的思想，但是这次我们找花费最小（即s到t费用最小）的增广路。

怎么实现呢？

看到那个（即s到t费用最小）了吗？

想到了什么？

最短路算法！

也就是说我们在找增广路时，把bfs换成spfa就可以了！

附上代码（相信看到这里，不用看我打的代码你都能自己打出来了）：

还有一点要注意：反向边的花费为正向边的相反数。

？

其实很好理解，如果那几个人不走这条路，那么这条路的钱就不用花了，但是因为刚才（前面走过的增广路）走过时花了钱，这次走反向边要退钱。

然后就是计算最大流和对应的最小费用了

这道题是P3381 【模板】最小费用最大流

附上完整代码：

另外，最小费用最大流还有更高效的zkw算法，由于有点复杂（作者太懒）就不讲解的，感兴趣的自行搜索。

本文发布于洛谷日报，特约作者：钱逸凡

原文地址：