[問題] ICPC 5713 疑似MST的問題
問題是這樣的
座標平面上有n個城市
每個城市都有自己的座標(x,y)和人口數
要建一個tree連接所有的城市
兩個城市的直線距離就是開路的成本
可以使用一次魔法無成本連結其中兩個城市
希望求a/b的最大值
a是用魔法連接的兩個城市的人口數總和
b是其他路的成本總和
看起來好像可以窮舉兩個城市後建MST找最佳解
但是這樣複雜度有O(n^3)
想問兩個解題方向
第一
有沒有演算法可以快一點處理"座標平面上的MST"
第二
先找出不使用魔法的MST
再窮舉兩個點用魔法連接
此時這兩個點的連線可能屬於MST或不屬於MST
如果不屬於MST的話要把形成的環上的最長的邊拿掉
有什麼演算法可以快一點達成這個目的?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.34.198.188
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1398340763.A.80C.html
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：