运筹学教学 | 十分钟快速掌握最大流算法（附C++代码及算例）

—“运筹教科书到底能给你啥？”

—“算法和实现离教科书有多远？”

—“问题解决能力到底从哪来？”

今天刚起床就接到了BOSS的 提·问·三·连

小编表示

收到直击内心的提问之后，小编决定

翻开教科书、打开编译器

在今天的运筹学·第二弹——最大流问题篇中

和大家一起寻找问题的答案!

运筹学·教学笔记 第二弹 —— 最大流问题篇 奉上！熟悉的攻略三连（问题、方法、实现）、熟悉的实践演示、熟悉的代码算例...手把手带你走上 运筹学·大佬 的征程！

＊

内容提要：

＊什么是最大流问题

＊求解最大流问题的算法

＊两种增广路算法

1.什么是最大流问题

最大流问题(maximum flow problem)是一种组合优化问题，即讨论如何充分利用装置的能力，使得运输的流量最大以取得最好的效果的问题。

在具体描述最大流问题前，我们先介绍几个网络流问题中常见的定义：

G = (V,E) 表示整个图.

V 表示整个图中的所有结点的集合.

E 表示整个图中所有边的集合. s 表示网络的源点

t 表示网络的汇点. 对于每条边(u,v), 有一个容量c(u,v) (c(u,v)>=0)

（如果c(u,v)=0，则表示(u,v)不存在在网络中。相反，如果原网络中不存在边(u,v)，则令c(u,v)=0.）

对于每条边(u,v) 有一个流量f(u,v).

在了解了些上述定义后，下面我们给出具体的问题描述：

（没错，就是你们常见的教科书内容来了！！）

好了，记笔记记笔记~~ 问题描述 part 教科书里面有基·础·范·本！！

2.求解最大流问题的算法

再次划重点记笔记！教科书上多只讲增广路算法！解决问题的算法不只一种，课本上篇幅有限，要想了解更多，还是要 自·己·学·操·作！！

然而和善如小编已经整理好这部分的资料打包送给各位...（没错，不要吝啬你们的夸奖...）

鉴于下面小编也会着重介绍增广路算法，有关最高标号预流推进算法的学习资料在这里为大家指路：

http://blog.csdn.net/KirinBill/article/details/60882828

(PS.致谢blog主人——大佬KirinBill~~~)

3.两种增广路算法

—增广路算法—

图2 残量网络与增广路算法

上面介绍了增广路解决最大流的思路，接下来我们介绍两种具体实现增广路方法的算法：

— Edmonds-Karp 算法

— Dinic 算法

代码及算例示例

代码（c++版本）

算例演示

算例示例

输入格式：

Input

6 9

1 2 8

1 3 7

2 4 9

2 5 3

2 3 5

3 5 9

4 6 7

5 4 6

5 6 10

PS. 需要输入两个整数n, m分布代表节点数和边数，

接下来每行3个整数x y z代表x、y之间路径的容量是z

输出结果为：

Output:

15

PS. 输出一个整数，表示图中最大流结果

算例演示

如上所示，我们输入的是第一个网络图，算法代码运行后的结果如第二个网络图所示，其中边上流量值如11/16，表示这条边的最大容量为16，而从s到t，这条边的路径能通过的最大流量为11。

上述代码仅供分享交流学习用，如有需要复制下面链接自取 ↓ ↓ ↓

http://paste.ubuntu.com/25584352/

或直接戳文章底部的 阅读原文，跳转代码页面！

参考书目：

[1] Operations Research - Applications and Algorithms (Wayne L. Winston)

[2] 刘汝佳, 算法竞赛入门经典（第2版） (算法艺术与信息学竞赛) P569 - P573

运筹学·教学笔记 第二弹 —— 最大流问题篇 画上句点！如果大家对 最大流问题 及 文中所叙内容 还有疑问或想要交流心得建议，欢迎移步留言区！

读至此，相信大家也都明白了开头的提问三连了~~教科书≠算法，教科书只会给我们列出 问题—方法 的框架，基于这些框架有许多算法、算法的实现、具体问题中的变化和运用...这些都需要我们自己主动去开拓、学习！

......不说了，小编要去自己开拓solo了！

—end—

编辑：谢良桢（1922193128@qq.com）

华中科技大学管理学院本科三年级

贺兴（hexing15@gmail.com）

华中科技大学管理学院本科三年级

代码：贺兴（hexing15@gmail.com）

华中科技大学管理学院本科三年级

指导老师：秦时明岳（professor.qin@qq.com）