最大流（Max Flow）学习笔记 1
好吧，在磨叽了 N 久之后，小菜我终于决定向图论进发了。为了庆祝我能稍稍理解最大流的思路，特此感谢“ACM 阿次魔”群中的各大牛们，以及白神和郭神，好吧，大牛们果然都是来自 ACM_DIY 的。ym 之。
本笔记只有思路，而且是最最入门级的思路。笔记最后附启蒙我的 PPT 下载=。=
老规矩，大牛们可以一笑而过或者选择围观，有兴趣的童鞋们可以一起研究研究。按下面按钮以阅读全文。
随便写写
所谓最大流，就是水一样哗哗哗地流过若干管道。而每个管道都有其自身的最大流量。然后你要找到从起点到终点时可以流过的最大流量。
问题提出
直接给出模型：
设定有向图 G = (V, E)，每条边都有给定的容量 Cv, u，其中：s 为发点，t 为收点。对于每一点边 (v, w)，最多可以有 Cv, u 个单位的流量通过。除发点和收点外，每个顶点的进入的流量必须等于发出的流量。
最大流量问题就是确定从 s 到 t 的最大流及流图。
简单思路
接下来是一个贪心（or 深搜？）的算法。即：
- 在残留图中找一条增长通路（从
s到t的通路）； - 流图中加上这个通路，流量加上这条通路的最小流量的管道的权值；（最大流量是最小信道的流量，多了也流不动）
- 调整残留图：一旦某条管道流完了，就把管道删掉，如果没流完，那幺减去流掉的值；
- 一直重复 1~3 直到没有通路。
这样就得到了“最大流”。
But
很重要的一点：不好意思，以上说的只是一种思路，而不是“正确”思路。
贪心策略不能保证最优！！！
很显然，如果上述的第一条通路换成如下的通路，错误性就显而易见了：
这样一来，就阻断了 s-b-d-t 的这样一条通路，所以贪心显然是错误的。但是不能贪心，也不能随机取啊，怎幺知道要先通哪条呢？
事实上，我们只要在上面的算法中动点小手脚就好了。
在每次找到一条通路之后，删边或者减小流量之后，在这条通路的反方向加上相应的可用流量即可。就像这样：
然后就可以再找通路了，接下来的一条通路就是（蓝边）：
然后我们再开始删边、加反方向可用流量，一直到没有通路为止。
为什么？(new)
为什幺要加一条回路呢？我开始不是很理解。于是我请教了 StarVae，下面是他的话：
Star VAE! 12:36:15
哦 反向边 是为了能够有后悔的机会 直接流一次 不一定就是最大流的
也就是说，反向边是为了可以让流往回流再继续下一次流的一个“过渡边”。Star VAE! 12:38:45
流量 是加上去了的 我们算流量 不是算a->b这段路上的流量 算的是s->t这个流量 按照你的意思 如果还需要减去的话 那应该是叫做 费用 而不是流量} **.死月| 12:39:05
喔} **.死月| 12:39:09
就是说 如果后悔了} **.死月| 12:39:18
是因为有更大的通过同一条路的流量} **.死月| 12:39:28
所以 只要加上去补差量就好了 是幺Star VAE! 12:39:43
恩 差不多吧
参考
好吧，本小菜是看着一个《数据结构第 19 讲：第 7 章（4）最短距离，网络流》的 ppt 学的，所以本文中的图是出自于那个 ppt，以及思路也是从那里灌输过来的。
有兴趣的童鞋们可以下载。可能比我自己写的学习笔记更易懂吧。
飞速下载 PPT（原下载链接已无法寻回，但是可以自行去网上搜索）