扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 最小生成树简单
单选题
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。