扫一扫二维码
进群一起备考
查看更多
当前 - 选择题 - 最小生成树困难
单选题
2017年5月第42题
收藏
分享
#数学与经济管理
#最小生成树
#第二版教材
#凯恩建议必须掌握
已知八口海上油井（编号从1#到 8#） 相互之间的距离（单位：海里）如下表所示，其中 1#油井离海岸最近为 5 海里。现从海岸开始铺设输油管道，经 1#油井将这些油井都连接起来，管道的总长度至少为（__）海里（为便于计量和维修，管道只能在油井处分叉）。
问题（1）
正确答案C
凯恩解析
本题考察的是 最小生成树（MST） 模型与 Kruskal 算法 的应用。
因为分叉只能在油井处，且从海岸只需接到 1#，所以总长度 = 海岸至 1# 的 5 海里 + 8 口井之间的最小生成树长度。
用 Kruskal 算法按权值从小到大选边并避免成环，可选取的 7 条边为：1#–5#（0.5）、7#–8#（0.5）、6#–7#（0.6）、4#–5#（0.7）、5#–8#（0.8）、2#–3#（0.9）、3#–8#（1.0），此时 8 个顶点全部连通。
MST 长度为 0.5+0.5+0.6+0.7+0.8+0.9+1.0=5.0 海里。 再加上海岸到 1# 的 5 海里，总最小长度为 5+5=10 海里。
选择选项 C。