单选题
题号 #6183567

工程师小张需要完成图1-27—5中所有区域的巡检工作,图中圆圈代表巡检地点,两点之间的连接线为可行的交通路径,连接线上所标识的数字为两点之间所需的交通费用(单位:元).从地点l开始完成巡检(不需按数字顺序也无须返回起点)所需的最少交通费用为(  )元。

进入在线模考

参考答案

C

答案解析

本题考查的是图论中的最小生成树。
首先找出路线的最小值,最小值为30,对应路径为1—2、5—6,然后找50的路径4—5,然后找60的路径7—8、70的路径5—7,最后把80的路径2—3连接起来,如图1—27—6所示。

最后需要全部连通,需注意此题巡检需要每个节点都走到,并且一次性走完,所以4、5、6的连通要调整,调整后如图1—27—7所示。

最后调整顺序为:1—2—3—4—6—5—7—8—400,所以,从地点1开始完成巡检(不需按数字顺序也无须返回起点)所需的最少交通费用为400元。
 

你可能感兴趣的试题

找试题 · 找答案 · 找资料 在线模考