查看更多
当前 - 选择题 - 最小生成树
简单
单选题
2012年5月第41题
#数学与经济管理
#最小生成树
#第二版教材
#凯恩建议必须掌握

开发商需要在某小区9栋楼房之间敷设自来水管道,使各楼都能连通,又能使总成本最低。 经勘察,各楼房之间敷设管道的路径和成本(单位:千元)如下图所示。

该项目的总成本至少需要(__)千元。

问题(1)
正确答案A
凯恩解析

本题考察的是最小生成树(MST) 的求解。
由于“管道只能在楼房处分叉”,问题可抽象为带权连通无向图的最小生成树。求解可用Kruskal 算法:将所有候选边按权值从小到大依次选取,跳过会形成回路的边,直到选满 n−1 条边(本题 n=9,需选 8 条)。
按图中权值由小到大选择,可先取所有不致成环的权值为 1 的边(4条),再取能把剩余连通分量连成一体且不成环的权值为 2 的边(3条),权值为 3 的边 1 条。
这样恰好得到 8 条边,MST 总成本 = 1+2+1+1+1+2+3+2 = 13(千元)
选择选项 A。

联系我们
隐私协议
用户协议
微信公众号
知乎
小红书
浙ICP备2021029036号
@2022-2026
嘉兴市安芯网络科技有限公司 版权所有