看板 [ Prob_Solve ]
討論串[問題] ICPC 5713 疑似MST的問題
共 2 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] ICPC 5713 疑似MST的問題
推噓0(0推 0噓 0→)留言0則，0人參與, 最新作者iamnotgm (伽藍之黑)時間10年前 (2014/04/24 19:59), 編輯資訊
1
0
1
內容預覽:
問題是這樣的. 座標平面上有n個城市. 每個城市都有自己的座標(x,y)和人口數. 要建一個tree連接所有的城市. 兩個城市的直線距離就是開路的成本. 可以使用一次魔法無成本連結其中兩個城市. 希望求a/b的最大值. a是用魔法連接的兩個城市的人口數總和. b是其他路的成本總和. 看起來好像可以窮
(還有132個字)
#2
Re: [問題] ICPC 5713 疑似MST的問題
推噓1(1推 0噓 1→)留言2則，0人參與, 最新作者DJWS (...)時間10年前 (2014/04/24 22:45), 10年前編輯資訊
0
0
2
內容預覽:
窮舉兩個城市是O(n^2)，MST是O(n^2)，所以總共是O(n^4)吧. 這題有a和b，其實也可以窮舉b. 窮舉MST上的每一條邊，把他拿掉，重新找魔法連接，使得a最大。理論上是有. http://en.wikipedia.org/wiki/Euclidean_minimum_spanning_
(還有66個字)
首頁
上一頁
1
下一頁
尾頁