题意分析

1. 问题背景

戈雷利安人通过空间跃迁通道征服星球，形成RGP网络（$Regional Gorelian Planetary Network$）。该网络是一个树形结构，其中：

• 初始星球：第一个被征服的星球成为$RGGG$（区域政府）所在地。
• 扩张规则：每个新星球连接到当前$RGP$网络中最近的已有星球（距离相等时选择先被征服的）。
• 优化目标：每年需要将$RGGG$重新定位到一个最佳星球，使得从网络中任意星球到$RGGG$的最大跃迁次数最小化。

2. 输入输出要求

• 输入：
  • 多组测试数据，每组以$N$（星球数）开头，$N=0$时终止。
  • 接下来$N$行按征服顺序给出星球$ID$和坐标$(X,Y,Z)$。
• 输出：
  • 最佳星球的$ID$（若唯一）或两个$ID$（若存在两个最佳且相邻的星球，按升序输出）。

3. 关键约束

• 网络结构：$RGP$网络是一棵树，边权为星球间的欧几里得距离。
• 最佳位置定义：最小化树的半径（即所有节点到中心节点的最大距离的最小值）。
• 解的特性：最佳位置为树的中心（可能是一个或两个相邻节点）。

解题思路

1. 树的性质与中心求解

• 树的直径：树上最长路径，其端点记为$u$和$v$。
• 中心性质：
  • 若直径为偶数长度，中心为唯一节点。
  • 若为奇数长度，中心为相邻的两个节点。
• 算法选择：
  1. 两次BFS/DFS求直径端点$u$和$v$。
  2. 从$u$到$v$的路径上找中点（即中心）。

2. 实现步骤

1. 构建$RGP$网络：
   • 按输入顺序处理星球，每个新星球连接到当前网络中最近的已有星球，形成树结构。
2. 求树的直径：
   • 任选一点（如$ID=1$），通过$BFS$找到最远点$u$。
   • 从$u$出发，$BFS$找到最远点$v$，$u$到$v$的路径即为直径。
3. 确定中心：
   • 记录$u$到$v$的路径，根据路径长度奇偶性输出中心节点。

3. 复杂度分析

• 构建树：$O(N^2)$（每新星球需比较所有已有星球）。
• 求直径：$O(N)$（两次BFS）。
• 总复杂度：$O(N^2)$，$N \leq 1000$，完全可行。

标程

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#define maxn 1010
 
using namespace std;
 
int n,id[maxn];
double x[maxn],y[maxn],z[maxn],dis[maxn][maxn],dp[maxn];
int path[maxn],pre[maxn];
vector<int> G[maxn];
 
double dist(int u,int v)
{
    double dx = x[u]-x[v];
    double dy = y[u]-y[v];
    double dz = z[u]-z[v];
    return sqrt(dx*dx+dy*dy+dz*dz);
}
 
void build()
{
    for(int i=1;i<=n;i++)
    {
        double maxl = 9999999;
        int obj=-1;
        for(int j=1;j<i;j++)
        {
            if(dis[id[i]][id[j]]<maxl)
            {
                maxl = dis[id[i]][id[j]];
                obj = j;
            }
        }
        if(obj==-1) continue;
        int u = id[i],v = id[obj];
        G[u].push_back(v);
        G[v].push_back(u);
    }
}
 
void dfs(int x,int fa,int len)
{
    dp[x] = len;
    for(int i=0;i<G[x].size();i++)
    {
        int u = G[x][i];
        if(u!=fa)
            dfs(u,x,len+1);
    }
}
 
void dfs1(int x,int fa,int len)
{
    dp[x] = len;
    pre[x] = fa;
    for(int i=0;i<G[x].size();i++)
    {
        int u = G[x][i];
        if(u!=fa)
            dfs1(u,x,len+1);
    }
}
 
int main()
{
    int p1,p2;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0) break;
        for(int i=0;i<=1005;i++)
            G[i].clear();
        memset(pre,0,sizeof(pre));
        memset(path,0,sizeof(path));
        memset(dis,0,sizeof(dis));
        memset(pre,0,sizeof(pre));
 
        for(int i=1;i<=n;i++)
        {
            scanf("%d%lf%lf%lf",&id[i],&x[i],&y[i],&z[i]);
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                dis[id[i]][id[j]] = dist(i,j);
            }
        }
        build();
        memset(dp,0,sizeof(dp));
        dfs(id[1],-1,0);
        double tmp = 0;
        for(int i=1;i<=n;i++)
        {
            if(dp[id[i]]>tmp)
            {
                tmp = dp[id[i]];
                p1 = id[i];
            }
        }
        memset(dp,0,sizeof(dp));
        dfs1(p1,-1,0);
        tmp = 0;
        for(int i=1;i<=n;i++)
        {
            if(dp[id[i]]>tmp)
            {
                tmp = dp[id[i]];
                p2 = id[i];
            }
        }
        int s = 0;
        for(int i=p2;i!=-1;i=pre[i])
        {
            path[++s] = i;
        }
        int mid = (s+1)/2;
        if(s&1)
        {
            printf("%d\n",path[mid]);
        }
        else
        {
            int a = path[mid],b = path[mid+1];
            if(a>b)
            {
                int t = a;
                a = b;
                b = t;
            }
            printf("%d %d\n",a,b);
        }
    }
    return 0;
}