扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 网络与最大流量中等
单选题
2025年11月第11题
中等
单选题
2025年11月第11题
#第二版教材
#必须掌握
下图所示为一条输油网络图，其中每条有向边上的数字表示管道的最大流量（单位：吨/小时）。试计算从 S 到 T 的最大流量 （问题1） ，并判断关闭哪一条路径 （问题2） 不影响系统的最大流量。
正确答案
A
本题考察的是网络最大流（Max-Flow）算法与割集分析。
直接用作图法求解。
那么总的流量就是 5+5+3+1+2 = 16。从图中可以看到 CD 的通路至始至终没有利用到，所以这条管线关闭不影响最大流量。
答案选择 A，A。