工程师小张需要完成图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元。
首先找出路线的最小值,最小值为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元。
你可能感兴趣的试题
A.5
B.6
C.7
D.8
A.A—B1—C1—D2—E
B.A—B2—C1—D1—E
C.A—B3—C2—D2—E
D.A—B2—C2—D3—E

