网络最大流

半个月前学了网络最大流，，然后弃坑。。。

半个月后。。。

原谅我使用了一些来自互联网的图。

基础概念

通俗地来讲网络最大流问题就是就是求从工厂最多可以发出多少货物，不至于超过道路的容量限制，与上述通俗概念不同的是每一条道路是一次性的。也就是每一辆车通过每一条道路都需要将这条道路的容量减去车的载重直至容量小于0（好像是废话），因为如果不是这样就可以理解成第一辆车载着n通过了，第二辆车可以继续从这里载着n通过。

严格的定义就是：给定一个有向图，和两个点–源点A和汇点G，点之间有连边，每条边有一个容量限制，网络流就是指由S点流到T点的一个可行流。最大流就是指所有可行流里面最大的流。

上方给出的图就是从A出发到G最大的流。

求解

首先需要引入一个剩余的概念：

从上图来看，左边代表的是这条道路的容量，右边代表的是这条道路剩下的流量。

贪心

自然地可以想到贪心，但是贪心却是错误的。大致的思路就像是dijkstra算法，每一次找所连边中剩余最大的那一个，很容易就可以找到例子推翻。

例如在上面的这个经典的图中，我们找到了1->2->4->6 这条增广路，得到了汇点最大的流是2然而答案显然不是2。任可以1->3->4->2->5->6 最大是3。那么如何得到这个3呢？

DINIC

DINIC的基本思路就是：

根据残量网络计算层次图。
在层次图中使用DFS进行增广直到不存在增广路
重复以上步骤直到无法增广

至于残量网络、层次图是什么，接下来用几个不同的思路来解决。

添加反向边

每插入一条边 $u$ 到 $v$ 的边权是 $w$ ，我们考虑添加一条反向的边权为0的边，也就是从 $v$ 到 $u$ 边权是0的边。这样做的目的是使程序可以走“回头路”。考虑上方的图，每当从一个点流向另一个点时，将这条边的反向边加上流量值，如果到了下一个点仍保留往回走的方案。

具体类似于这样：

//读边
addedge(u,v,s);
addedge(v,u,0);

//内部dfs，这里的s指的是遍历到的边的剩余流量。
e[i].w-=s; e[i^1].w+=s;
/*^1的作用就是奇数-1偶数+1。
相当于就是正向边-s，反向+s
*/

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。