10算法设计与分析---网络流

1 .东南大学计算机学院 方效林 网络流

2 .本章内容 网络流 2

3 .本章内容 给定有向图 ，边上 权值表示 容量，给定源点 和汇点 ，求 到 可流过的最大流量是多少？   3 s t 16 13 12 20 4 9 7 14 4

4 .网络流 只考虑单向边的图，双向的图可通过增加虚拟节点的方式 变 换为单向边的图 4 s t 16 13 12 20 4 9 7 14 4 10 10 s t 16 13 12 20 4 9 7 14 4

5 .网络流 给定有向图 ，边上 权值表示 容量，给定源点 和汇点 ，求 到 可流过的最大流量是多少？   5 s t 100 100 100 100 100

6 .网络流 只考虑单向边的图，双向的图可通过增加虚拟节点的方式 变 换为单向边的图 6 s t 10 10 10 10 10 10 s t 10 10 10 10 10 10 10

7 .网络流 简单想法 从源到汇找一条可行路径，塞满流量 7 s t 100 100 100 100 100 s t 100 100 100 100 100 简单想法 最优解

8 .网络流 取消部分设置好的流 对一些设置好的流可能反悔 8 s t 100 100 100 100 100 s t 100 100 100 100 100 s t 100 100 100 100 100

9 .网络流 残留网络 某一条边使用了多少流量，则其反方向设置多少可反悔的流量 9 s t 100 100 100 100 100 s t 100 100 100 100 100  

10 .网络流 Fold-Fulkerson 算法 在残留网络从源到汇找一条可行路径，塞满流量 10   s t 100 100 100 100 100 s t 100 100 100 100 100 s t 100 100 100 100 100

11 .网络流 Fold-Fulkerson 算法 在残留网络从源到汇找一条可行路径，塞满流量 11 s t 100 100 100 100 100   s t 100 100 100 100 100 s t 100 100 100 100 100 + =

12 .网络流 Fold-Fulkerson 算法 在残留网络从源到汇找一条可行路径，塞满流量 12   s t 16 13 12 20 4 9 7 14 4 初始网络

13 .网络流 Fold-Fulkerson 算法 在残留网络从源到汇找一条可行路径，塞满流量 13   s t 16 13 12 20 4 9 7 14 4 0 0 0 0 0 0 0 0 0 残留网络 1 路径上流为 4

14 .网络流 Fold-Fulkerson 算法 在残留网络从源到汇找一条可行路径，塞满流量 14   s t 12 13 8 20 4 5 7 10 0 4 4 4 0 4 0 0 4 0 残留网络 2 路径上流为 4

15 .网络流 Fold-Fulkerson 算法 在残留网络从源到汇找一条可行路径，塞满流量 15   s t 12 9 4 16 0 5 7 10 0 4 8 4 4 4 4 4 4 0 残留网络 3 路径上流为 4

16 .网络流 Fold-Fulkerson 算法 在残留网络从源到汇找一条可行路径，塞满流量 16   s t 8 9 4 12 4 9 7 10 0 8 8 0 8 4 4 0 4 0 残留网络 4 路径上流为 7

17 .网络流 Fold-Fulkerson 算法 在残留网络从源到汇找一条可行路径，塞满流量 17   s t 8 2 4 5 4 9 0 3 0 8 8 0 15 4 11 0 11 7 残留网络 5 路径上流为 4

18 .网络流 Fold-Fulkerson 算法 在残留网络从源到汇找一条可行路径，塞满流量 18   s t 4 2 0 1 4 9 0 3 0 12 12 0 19 4 11 0 11 7 残留网络 6 路径上流为 0

19 .网络流 Fold-Fulkerson 算法 在残留网络从源到汇找一条可行路径，塞满 流量 遇到下面这个图，再遇到搜索可行路径时每次都经过权值为 1 那条边，时间复杂度很高 19   s t 10 6 10 6 10 6 1 10 6

20 .网络流 Edmonds-Karp 算法 使用 BFS 搜索可行路径，时间复杂度   20 s t 10 6 10 6 10 6 1 10 6