※ 引述《iamnotgm (伽蓝之黑)》之铭言：
: 问题是这样的
: 座标平面上有n个城市
: 每个城市都有自己的座标(x,y)和人口数
: 要建一个tree连接所有的城市
: 两个城市的直线距离就是开路的成本
: 可以使用一次魔法无成本连结其中两个城市
: 希望求a/b的最大值
: a是用魔法连接的两个城市的人口数总和
: b是其他路的成本总和
: 看起来好像可以穷举两个城市后建MST找最佳解
: 但是这样复杂度有O(n^3)
穷举两个城市是O(n^2)，MST是O(n^2)，所以总共是O(n^4)吧
这题有a和b，其实也可以穷举b
穷举MST上的每一条边，把他拿掉，重新找魔法连接，使得a最大。
: 想问两个解题方向
: 第一
: 有没有算法可以快一点处理"座标平面上的MST"
理论上是有
http://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree
实际上我不清楚...
: 第二
: 先找出不使用魔法的MST
: 再穷举两个点用魔法连接
: 此时这两个点的连线可能属于MST或不属于MST
: 如果不属于MST的话要把形成的环上的最长的边拿掉
: 有什么算法可以快一点达成这个目的?
second-best minimum spanning tree problem