查看更多
当前 - 选择题 - 网络与最大流量
中等
单选题
2024年5月第25题

从油田S到大城市T经过五个中转站A、B、C、D、E的输油管道网络如下图。图中每段管道旁的数字注明了该段管道的输油能力(每天输油万吨数)。根据该图,从S到T的总输油能力为(__)万吨/天。

问题(1)
浓缩知识点

最大流问题是网络流领域的经典问题,核心是求解从源节点到汇节点的最大可行传输能力,广泛应用于输油管道规划、通信网络带宽分配、物流路径流量调度等场景。求解最大流常用增广路径思路,其中贪心式选择增广路径的方式操作简便,但存在局限性,部分场景下无法得到正确结果;更严谨的是标号法,属于福特-富尔克森算法的典型实现,通过正向寻找可增流路径、反向调整残留网络流量的迭代流程,能精准计算最大流。该问题的核心理论是最大流最小割定理,即源点到汇点的最大流数值,等于能将源、汇节点分隔开的最小割集的总容量,最小割是所有可分离源汇的边集合中总容量最小的那个集合,这一定理为最大流的验证与求解提供了关键依据。

正确答案
C

此题考察最大流量的相关问题。具体计算方法可以看我视频(B站芝士架构凯恩最大流)。
首先断开 SADT,再断开 SACDT,再断开 SBET,再断开 SBCET。
当然你可以选取其他方法(注意这种贪心算法是有缺陷的,对于此题这里的其他方法可能得不到最大流 19,但是这种方法比较容易简单,否则要用标号法正推逆推复杂度加倍,在真实的考试中,假如一种路径没有答案,多试几种路径选择方法)。
最后把流量累加 5+5+5+4 = 19。



联系我们
隐私协议
用户协议
微信公众号
知乎
小红书
浙ICP备2021029036号
@2022-2026
嘉兴市安芯网络科技有限公司 版权所有