查看更多
当前 - 选择题 - 网络与最大流量
中等
单选题
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
嘉兴市安芯网络科技有限公司 版权所有