问题是这样的
座标平面上有n个城市
每个城市都有自己的座标(x,y)和人口数
要建一个tree连接所有的城市
两个城市的直线距离就是开路的成本
可以使用一次魔法无成本连结其中两个城市
希望求a/b的最大值
a是用魔法连接的两个城市的人口数总和
b是其他路的成本总和
看起来好像可以穷举两个城市后建MST找最佳解
但是这样复杂度有O(n^3)
想问两个解题方向
第一
有没有算法可以快一点处理"座标平面上的MST"
第二
先找出不使用魔法的MST
再穷举两个点用魔法连接
此时这两个点的连线可能属于MST或不属于MST
如果不属于MST的话要把形成的环上的最长的边拿掉
有什么算法可以快一点达成这个目的?