高项题库-2014下-综合知识-第68题

高项题库-2014下-综合知识第68题(单选题)
煤气公司想要在某地区高层住宅楼之间铺设煤气管道并与主管道相连,位置如下图所示,节点代表各住宅的楼和主管道位置,线上数字代表两节点间距离(单位:百米),则煤气公司铺设的管道总长最短为()米。
图片[1]-高项题库-2014下-综合知识-第68题-象网
A.1800
B.2200
C.2000
D.2100

【答案】B
【解析】
图片[2]-高项题库-2014下-综合知识-第68题-象网
(一)这是求最小支撑树的问题。使用破圈法求解,求解步骤如下:
所谓破圈法就是任取一个圈,从圈中去掉一条权最大的边(如果有两条或两条以上的边都是权最大的边,则任意去掉其中一条)。在余下的图中,重复这个步骤,直至得到一个不含圈的图为止,这时的图便是最小树。
(二)也可以使用穷举法

© 版权声明
THE END
喜欢就支持一下吧
点赞13 分享