煤气公司想要在某地区高层住宅楼之间铺设煤气管道并与主管道相连，位置如下图所示，节点代表各住宅的楼和主管道位置，线上数字代表两节点间距离（单位：百米），则煤气公司铺设的管道总长最短为 （ ） 米
- A.1800
- B.2200
- C.2000
- D.2100
正确答案及解析
正确答案
B
解析
这是一道最小生成树的问题，可以采用克鲁斯卡尔算法。依次寻找连通每个节点之间的最小距离（最小边），如果和已选取的边构成回路，则放弃，选取次小边。技巧是边的选择方案不构成回路，最后连通节点的边的数量为N-1条，N为节点数。题目中，间距最小的是5号楼到1号楼的间距为3；间距次小的是3号楼到4号楼的间距为4；然后是1号楼到4号楼的间距为5，或者4号到5号楼的间距为5；5号楼到6号楼的最小间距为5；2号楼到6号楼的最小间距为5，结果为3+4+5+5+5=22。所以结果为22×100=2200（米）。
包含此试题的试卷
你可能感兴趣的试题
-
- A.V(S2)和P(S4)
- B.P(S2)和V(S4)
- C.P(S2)和P(S4)
- D.V(S2)和V(S4)
- 查看答案
-
- A.V（S1）P（S2）和V（S3）
- B.P（S1）V（S2）和V（S3）
- C.V（S1）V（S2）和V（S3）
- D.P（S1）P（S2）和V（S3）
- 查看答案
-
- A.P（S4）和V（S4）V（S5）
- B.V（S5）和P（S4）P（S5）
- C.V（S3）和V（S4）V（S5）
- D.P（S3）和P（S4）V（P5）
- 查看答案
-
- A.P(S3)和V(S4)V(S5)
- B.V(S3)和P(S4)P(S5)
- C.P(S3)和P(S4)P(S5)
- D.V(S3)和V(S4)V(S5)
- 查看答案
-
- A.P（S2）和P（S4）
- B.P（S2）和V（S4）
- C.V（S2）和P（S4）
- D.V（S2）和V（S4）
- 查看答案