問題是這樣的
座標平面上有n個城市
每個城市都有自己的座標(x,y)和人口數
要建一個tree連接所有的城市
兩個城市的直線距離就是開路的成本
可以使用一次魔法無成本連結其中兩個城市
希望求a/b的最大值
a是用魔法連接的兩個城市的人口數總和
b是其他路的成本總和
看起來好像可以窮舉兩個城市後建MST找最佳解
但是這樣複雜度有O(n^3)
想問兩個解題方向
第一
有沒有演算法可以快一點處理"座標平面上的MST"
第二
先找出不使用魔法的MST
再窮舉兩個點用魔法連接
此時這兩個點的連線可能屬於MST或不屬於MST
如果不屬於MST的話要把形成的環上的最長的邊拿掉
有什麼演算法可以快一點達成這個目的?