我们想象一下自来水厂到你家的水管网是一个复杂的有向图，每一节水管都有一个最大承载流量。自来水厂不放水，你家就断水了。但是就算自来水厂拼命的往管网里面注水，你家收到的水流量也是上限（毕竟每根水管承载量有限）。你想知道你能够拿到多少水，这就是一种网络流问题。

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

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

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

最大流

最小费用最大流

何为最大流问题？

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

结合图示理解：

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

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

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

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

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

然后我们有

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

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

具体怎么操作呢？

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

具体操作：

找增广路：

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

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

那代码是长这样的吗?

当然不是，万一第一次流错了使得这样的流法无法得到最大流怎么办？ 还是以刚才那张图为例，为了防止你再翻上去，我直接再放一次：

如果你第一次的增广路是：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。

再找一次增广路，这次我们找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//最小费用最大流的EK算法 maxflow=0; cost=0; int mi; register int i; while(spfa()){ mi=inf; for(i=t;i!=s;i=pre[i].fa)mi=min(mi,node[pre[i].adge].val); for(i=t;i!=s;i=pre[i].fa){ node[pre[i].adge].val-=mi; node[pre[i].adge^1].val+=mi; } maxflow+=mi; cost+=mi*dist[t]; //本增广路最多能流的流量*从s到t的单位费用 } return maxflow; }

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

附上完整代码：