问题是这样的 座标平面上有n个城市 每个城市都有自己的座标(x,y)和人口数 要建一个tree连接所有的城市 两个城市的直线距离就是开路的成本 可以使用一次魔法无成本连结其中两个城市 希望求a/b的最大值 a是用魔法连接的两个城市的人口数总和 b是其他路的成本总和 看起来好像可以穷举两个城市後建MST找最佳解 但是这样复杂度有O(n^3) 想问两个解题方向 第一 有没有演算法可以快一点处理"座标平面上的MST" 第二 先找出不使用魔法的MST 再穷举两个点用魔法连接 此时这两个点的连线可能属於MST或不属於MST 如果不属於MST的话要把形成的环上的最长的边拿掉 有什麽演算法可以快一点达成这个目的? --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.34.198.188 ※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1398340763.A.80C.html