1. 什么是网络流

网络流(network-flows)是一种类比水流的解决问题方法,与线性规划密切相关。网络流的理论和应用在不断发展,出现了具有增益的流、多终端流、多商品流以及网络流的分解与合成等新课题。网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。

——摘自度娘百科

2. 什么是最大流问题

管道网络中每条边的最大通过能力(容量)是有限的,实际流量不超过容量。
最大流问题(maximum flow problem),一种组合最优化问题,就是要讨论如何充分利用装置的能力,使得运输的流量最大,以取得最好的效果。

——还是摘自度娘百科

通俗地说就是把图看成一个管道网络,从起点(这个是可以指定的)以一定速度灌水,问最大以多快的速度灌,水不会溢出。

3. 怎么求最大流?

1. 前言

目前我只学了增广路算法……= ̄ω ̄=

而且还是用深度优先搜索实现的增广路算法。

你要是看不起dfs……那你就别看呀!╭(╯^╰)╮

下面的话可能要学完了最大流才能看得懂,看不懂也是完全没关系的

我先看了看刘汝佳的小紫书,上面讲:“很容易找出让它很慢的例子”。然而我想了想也没觉得会很慢啊,每次增广最坏的复杂度是O(N),怎么会被卡呢……然后我又问了问神犇pyh,他(或她或它)说ta一直写的是dfs啊。于是我抱着挑战权威的心态写出了dfs版的增广路算法。然后……成功了。

然后我发现各种最大流算法的代码中建图都记录了两个值:每条边的流量与每条边的流量上限,然后根据流量上线-流量得到残量。我就想:如果我只保存残量难道不行吗?然后我就实践了一下,发现的确实可以的……

所以后面的代码风格看起来可能和网上的大部分代码是不同的……

(这个故事告诉我们不要迷信!实践出真知)

2. 思路

先定义一下:
残量:对于一条边来讲,它的残量就是它的最大流量减去它当前的实际流量。

然而思路是非常简单的。
1. 建图,每条边存3个值:这条边的起点,终点与残量。对于每条图中的边,它的残量初始值就是它的最大流量(因为一开始所有的边的实际流量都为0啊)。其次,我们还要建立反向边(就是对于每条从点u到点v的边,它的反向边就是一条从v到u的边),它的残量初始值为0。为什么呢?简单地说就是让程序有后悔的余地,就是说如果一开始把某条边的实际流量加多了,导致无法得到最大流,就可以通过反向边减回来。这后面看代码你就明白反向边是干什么用的了。

  1. 找增广路,找增广路时更新最大流。一直循环这个步骤,直到找不到增广路为止。

  2. 输出答案。

3. 具体做法

怎么找增广路?

其实就是找一条从起点到终点的路径(当然这条路径上的最小残量要>0)。对于这条路径上的每条边的流量,都加上这个路径上的最小残量(其实就是这些边的残量都减去这个路径上的最小残量),并且这些边的反向边的残量都加上这个路径上的最小残量(也就反向边的流量都减去最小残量)。

这个做法是很简单易懂的,相信聪明的你肯定琢磨一下就知道为什么要这么做了。(其实我是自己想出来的哇哈哈哈又开始飘了

用bfs是可以做的。但是dfs不是更简单吗?代码都不知道短了多少。回溯的时候直接修改边的残量就行了。而bfs还需要搞个变量存每个点的前驱,真是麻烦。

还有一些详细的见代码吧。

dfs找增广路的代码:

至于具体整个代码怎么搞,就看下面的模板题&代码吧!

4. 模板题&代码

1. Flow Problem HDU - 3549

传送门= ̄ω ̄=

代码:

2. Drainage Ditches POJ - 1273

传送门= ̄ω ̄=