※ 引述《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://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1398350751.A.5A8.html ※ 编辑: DJWS (111.250.61.1), 04/24/2014 22:57:48