[問題] ICPC 5713 疑似MST的問題
看板Prob_Solve (計算數學 Problem Solving)作者iamnotgm (伽藍之黑)時間10年前 (2014/04/24 19:59)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/2 (看更多)
問題是這樣的
座標平面上有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 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
