北京大学ACM暑期课讲义-网络流.pdf

网络流算法 北京大学信息学院 郭炜 本讲义部分内容引自李晔晨叶天扬斯文俊等同学的讲义，以及网上讲义  给定一个有向图G=(V,E)，把图中的边看作 管道，每条边上有一个权值，表示该管道 的流量上限。给定源点s和汇点t，现在假 设在s处有一个水源，t处有一个蓄水池， 问从s到t的最大水流量是多少  网络流图里，源点流出的量，等于汇点流 入的量，除源汇外的任何点，其流入量之 和等于流出两之和 解决最大流的Ford-Fulkerson算 法  基本思路很简单,每次用dfs从源到汇找一 条可行路径， 然后把这条路塞满。这条 路径上容量最小的那条边的容量，就是这 次dfs所找到的流量。然后对于路径上的 每条边，其容量要减去刚才找到的流量。 这样，每次dfs都可能增大流量，直到某次 dfs找不到可行路径为止，最大流就求出 来了 这个想法是否正确？ a 100 100 s 100 t 100 100 b  如果我们沿着s-a-b-t路线走 仅能得到一个100的流 a 100 100 实际上此图存在流量 s 100 为200的流 t 100 100 b  问题出在过早地认为边a → b上流量不为0，因而“ 封锁”了流量继续增大的可能。  一个改进的思路：应能够修改已建立的流网络，使得 “不合理”的流量被删掉。  一种实现：对上次dfs时找到的流量路径上的边，添 加一条“反向”边，反向边上的容量等于上次dfs时 找到的该边上的流量，然后再利用“反向”的容量和 其他边上剩余的容量寻找路径。 a 100 100 s 100 第一次dfs后: t 100 100 b 第一次dfs后，添加反向边得到的新图： a 100 100 s 100 t 100 100