煤气公司想要在某地区高层住宅楼之间铺设煤气管道并与主管道相连，位置如下图所示，节点代表各住宅楼和主管道位置，线上数字代表两节点间距离(单位：百米)。则煤气公司铺设的管道总长最短为( )米。

admin2016-05-11 48

问题煤气公司想要在某地区高层住宅楼之间铺设煤气管道并与主管道相连，位置如下图所示，节点代表各住宅楼和主管道位置，线上数字代表两节点间距离(单位：百米)。则煤气公司铺设的管道总长最短为( )米。

选项 A、1800
B、2200
C、2000
D、2100

答案B

解析这是求最小支撑树的问题，可使用破圈法求解。所谓破圈法就是任取一个圈，从圈中去掉一条权值最大的边(如果有两条或两条以上的边都是权值最大的边，则任意去掉其中一条)。在余下的图中，重复这个步骤，直至得到一个不含圈的图为止，这时的图便是最小树。
求解步骤如下：(红线表示该条路径删除)
(1)先找出一个中心点，圈1，因为圈1与所有点都有联系，则删除从圈1出发的两点距离最长的9，可得：