ACM试题1181 Bus Terminals.pptVIP

Bus Terminals IOI’2002 Day2 Problem2 问题描述 给定n个车站 找两个车站做总站，每个车站必须连到其中的一个总站 两个车站不能直接相连，必须通过总站连接 求使得任意两个车站之间的距离最短的方案，输出该方案下两车站间的最大距离 问题抽象 在平面上给出n个点，从中选择两个点连在一起，并找出一种把其他的点连到这两个点上的方案，使得任意两点间的最长路径距离最短 任意两点(x1,y1)，(x2,y2)之间的距离是abs(x2-x1)+abs(y2-y1) 欧几里德最小直径生成树问题 输入输出 输入：n+1行。第一行是车站数目n。接下来n行是n个点的横纵坐标 输出：所求方案下两点间的最大距离 例子 问题规模 车站数目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，则任意两点之间的最大距离是： max(r1+d12+l1，r1+r2，l1+l2) 如何在O(n)时间内得到r1,r2,l1,l2？ 一个自然的想法 遍历每个点，计算它到H1、H2的距离d1、d2 若d1d2，连到H1，更新r1，r2 否则，连到H2，更新l1，l2 时间复杂度O(n)，但是是错误的！ 不能根据d1和d2来判断该点连到H1还是H2 看例子 换个角度看 设取到d(H1, p1) = r1的点为p1，则所有 d(H1,q)r1的点q必然都连到了H2上 若存在某一点s满足d(H1, s) r1但s连到了H2上，我们来证明可以把这个点连到H1上而不增加两点间的最远距离。 改动后，可能影响三项：r1+r2，l1+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) 实现时注意问题 题目中没说两个车站不能重合，所以要考虑两个车站重合的情况。可以用O(n2)单独计算 测试数据时限要求很严，大家可以想想有没有更好的算法，或者这个算法有没有什么可以优化的地方。 * * 刘国栋 2003.7.19 *