
刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!
单选题
下图标明了六个城市(A~F )之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路,使各个城市之间均可通过高速公路通达,至少要改造总计( )公里的公路,这种总公里数最少的改造方案共有(请作答此空 )个。


A
B
C
D
使用微信搜索喵呜刷题,轻松应对考试!
答案:
解析:
根据题目描述和图例,我们需要将六个城市(A~F)通过改造公路使其都能通过高速公路相互通达。这实际上是一个求最小支撑树的问题,目的是选取部分公路使得所有城市都能相互连通,并且总长度最短。
我们可以按照以下步骤来求解:
- 从任意一个点开始,例如A,先连接A与其他点中距离最短的边,这里是AE。
- 然后连接剩下的点中与A或E相连的最短边,可以是AB或AF。
- 接着继续连接剩下的点中与已连接的点集相连的最短边,如AF或BF。
- 再连接剩下的点中与已连接的点集相连的最短边FD。
- 最后连接剩下的点中与已连接的点集相连的最短边CD。
按照这个方案,我们选择的公路为AE、AB、AF、FD、CD,总长度为1300公里。这是所有可能的改造方案中总长度最短的方案之一。因此,至少要改造总计1300公里的公路,且这种总公里数最少的改造方案有C个。
创作类型:
原创
本文链接:下图标明了六个城市(A~F )之间的公路(每条公路旁标注了其长度公里数)。为将部分公路改造成高速公路
版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!



