ACM试题1181 Bus Terminals

《ACM试题1181 Bus Terminals》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、BusTerminalsIOI’2002Day2Problem2刘国栋2003.7.19问题描述给定n个车站找两个车站做总站，每个车站必须连到其中的一个总站两个车站不能直接相连，必须通过总站连接求使得任意两个车站之间的距离最短的方案，输出该方案下两车站间的最大距离问题抽象在平面上给出n个点，从中选择两个点连在一起，并找出一种把其他的点连到这两个点上的方案，使得任意两点间的最长路径距离最短任意两点(x1,y1)，(x2,y2)之间的距离是abs(x2-x1)+abs(y2-y1)欧几里德最小直径生成树问题输入输出输入：n+1行。第一行是车站数目n。接下来n行是n个点的横纵坐标输出：所求方案

2、下两点间的最大距离例子问题规模车站数目N：2<=N<=500点的坐标：<=5000数据规模很大暴力算法先穷举所有中心的选法：O(n2)对每种中心的选法，穷举两个点之间的距离，找最大值：O(n2)所有最大值的最小值就是答案复杂度：O(n4)5004，难以忍受考虑单中心情况暴力算法是O(n3)可以在O(n2)内完成：穷举中心的选法对每种选法，遍历每个点，记录到中心的最大距离r1和次大距离r2则min(r1+r2)为所求时间代价：O(n2)两个中心的情况如果我们知道了两个中心H1和H2（距离为d12），以及连到H1的点的最大距离r1和次大距离r2，以及连到H2的点的最大距离l1和次大距离l2，

3、则任意两点之间的最大距离是：max(r1+d12+l1，r1+r2，l1+l2)如何在O(n)时间内得到r1,r2,l1,l2？一个自然的想法遍历每个点，计算它到H1、H2的距离d1、d2若d1r1的点q必然都连到了H2上若存在某一点s满足d(H1,s)

4、l2，r1+d12+l1。后两项会使最大距离减小，我们只考虑第一项易知只有当d(H1,s)>r2的时候才可能通过r1+r2这个部分影响最远距离。但因为r1+d12+l1>=r1+d12+d(H2,s)>=r1+d(H1,s)所以这一部分总是小于r1+d12+l1的。这样改变不会使最大距离增大。于是，在确定了两个中心H1和H2后，我们只需要再确定连到H1的距离最远的点就可以了如果我们在确定了H1之后，把各个点按照对H1的距离排序，然后按降序遍历各个点，则r1、r2、l1、l2均可以在常数时间内得到算法的复杂度是O(n3)实现时注意问题题目中没说两个车站不能重合，所以要考虑两个车站重合的情况

5、。可以用O(n2)单独计算测试数据时限要求很严，大家可以想想有没有更好的算法，或者这个算法有没有什么可以优化的地方。ThankYou