刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

单选题

某运输网络图(见图1-3)有A~E五个结点,结点之间标有运输方向箭线,每条箭线旁标有两个数字,前一个是单位流量的运输费用,后一个是该箭线所允许的单位时间内的流量上限。从结点A到E可以有多种分配运输量的方案。如果每次都选择最小费用的路径来分配最大流量,则可以用最小总费用获得最大总流量的最优运输方案。该最优运输方案中,所需总费用和达到的总流量分别为 (56) 。

A
4,5
B
12,16
C
60,11
D
71,11
使用微信搜索喵呜刷题,轻松应对考试!

答案:

C

解析:

根据题目中的算法,每次选择最小费用的路径来分配最大流量。具体计算如下:
① 走路径ACBE,价格分别是1、2、1,最大流量是5,费用是(1+2+1)×5=20,用完后CB断开,AC剩下3,BE剩下2;
② 走路径ABE,价格分别是4、1,最大流量是2,费用是(4+1)×2=10,用完后BE断开,AB剩下8;
③ 走路径ACDE,价格分别是1、3、2,最大流量是3,费用是(1+3+2)×3=18,用完后AC断开,CD剩下7,DE剩下1;
④ 走路径ABDE,价格分别是4、6、2,最大流量是1,费用是(4+6+2)×1=12,用完后DE断开,AB剩下7,BD剩下1;
至此没有了可行的通路,计算完成。全部流量为5+2+3+1=11,费用为20+10+18+12=60。因此,所需总费用和达到的总流量分别为60和11,选择C。

创作类型:
原创

本文链接:某运输网络图(见图1-3)有A~E五个结点,结点之间标有运输方向箭线,每条箭线旁标有两个数字,前一个

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share