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

单选题

下图标明了六个城市(A~F )之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计( )公里的公路,这种总公里数最少的改造方案共有(请作答此空 )个。

A
1
B
2
C
3
D
4
使用微信搜索喵呜刷题,轻松应对考试!

答案:

C

解析:

根据题目描述和图例,我们需要将六个城市(A~F)通过改造公路使其都能通过高速公路相互通达。这实际上是一个求最小支撑树的问题,目的是选取部分公路使得所有城市都能相互连通,并且总长度最短。

我们可以按照以下步骤来求解:

  1. 从任意一个点开始,例如A,先连接A与其他点中距离最短的边,这里是AE。
  2. 然后连接剩下的点中与A或E相连的最短边,可以是AB或AF。
  3. 接着继续连接剩下的点中与已连接的点集相连的最短边,如AF或BF。
  4. 再连接剩下的点中与已连接的点集相连的最短边FD。
  5. 最后连接剩下的点中与已连接的点集相连的最短边CD。

按照这个方案,我们选择的公路为AE、AB、AF、FD、CD,总长度为1300公里。这是所有可能的改造方案中总长度最短的方案之一。因此,至少要改造总计1300公里的公路,且这种总公里数最少的改造方案有C个。

创作类型:
原创

本文链接:下图标明了六个城市(A~F )之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路

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

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

分享考题
share