→ dreamoon:幫原PO附上second-best minimum spanning tree的連結 04/25 00:58
※ 引述《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
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.250.61.1
※ 文章網址: http://www.ptt.cc/bbs/Prob_Solve/M.1398350751.A.5A8.html
※ 編輯: DJWS (111.250.61.1), 04/24/2014 22:57:48