扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 网络与最大流量中等
单选题
2025年11月第11题
中等
单选题
2025年11月第11题
#第二版教材
#必须掌握
下图所示为一条输油网络图,其中每条有向边上的数字表示管道的最大流量(单位:吨/小时)。试计算从 S 到 T 的最大流量 (问题1) ,并判断关闭哪一条路径 (问题2) 不影响系统的最大流量。

正确答案
A
本题考察的是网络最大流(Max-Flow)算法与割集分析。
直接用作图法求解。





那么总的流量就是 5+5+3+1+2 = 16。从图中可以看到 CD 的通路至始至终没有利用到,所以这条管线关闭不影响最大流量。
答案选择 A,A。
