信息系统项目管理师题库/单项选择题

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

  • A1800
  • B2200
  • C2000
  • D2100
参考答案： B
解题思路： （一）这是求最小支撑树的问题。使用破圈法求解，求解步骤如下：
12图片1_副本.png
所谓破圈法就是任取一个圈，从圈中去掉一条权最大的边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条）。在余下的图中，重复这个步骤，直至得到一个不含圈的图为止，这时的图便是最小树。
（二）也可以使用穷举法

>>>立即刷题
相关动态
热点动态
版权所有：广州金猫教育科技有限公司

粤公网安备 44010602006255号

粤ICP备13087584-1号