题意分析

我们需要为分布在平面上的多个哨所（outposts）建立一个无线通信网络。通信方式有两种：

1. 卫星通信：任意两个拥有卫星信道的哨所可以直接通信，无论它们之间的距离有多远。
2. 无线电通信：两个哨所之间的距离不能超过$D$才能直接通信。所有哨所的无线电设备功率相同，因此$D$是全局统一的。

目标是确定最小的$D$值，使得所有哨所之间至少存在一条通信路径（直接或间接）。已知有$S$个卫星信道，且哨所的数量$P$满足$S < P \leq 500$。

解题思路

这个问题可以建模为图的最小生成树（MST）问题：

1. 图的构建：将每个哨所看作图中的一个顶点，顶点之间的边权是它们之间的欧几里得距离。
2. 最小生成树：我们需要找到一棵生成树，使得树中最长的边尽可能小。这是因为：
   • 生成树确保了所有顶点是连通的。
   • 卫星信道可以替代生成树中最长的$S-1$条边（因为$S$个卫星信道可以连接$S$个哨所，形成$S-1$条无需无线电的边）。
   • 因此，剩下的最长边就是所需的$D$值。

具体步骤如下：

1. 计算所有哨所两两之间的距离，得到边的集合。
2. 对这些边按距离从小到大排序。
3. 使用Kruskal算法构建最小生成树，记录生成树中所有边的长度。
4. 生成树中第$(P-S)$大的边就是答案（因为最大的$S-1$条边可以用卫星信道替代）。

实现步骤

1. 输入处理：

   • 读取测试用例数量$N$。
   • 对于每个测试用例，读取卫星信道数量$S$和哨所数量$P$。
   • 读取每个哨所的坐标$(x_i, y_i)$。

2. 计算距离：

   • 对于每对哨所$(i, j)$，计算欧几里得距离：$$d = \sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}$$
   • 将所有距离存储为边的集合。

3. 排序和Kruskal算法：

   • 将边按距离从小到大排序。
   • 初始化并查集（Union-Find）结构，用于管理连通分量。
   • 遍历排序后的边，使用Kruskal算法构建最小生成树，记录生成树中的边长度。

4. 输出结果：

   • 生成树中第$(P-S)$大的边长度即为答案（因为最大的$S-1$条边可以用卫星信道替代）。
   • 输出结果保留两位小数。

代码实现

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
struct path
{
    int x,y;
    double w;
}a[500*500+50];
int x[505];
int y[505];
double ans[505];
int f[505];
double dis(int i,int j)
{
    double d=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
    return d;
}
double cmp(path a,path b)
{
    return a.w<b.w;
}
int find(int x)
{
    int r=x;
    while(f[r]!=r)
    {
        r=f[r];
    }
    return r;
}
void merge(int x,int y)
{
    int xx=find(x);
    int yy=find(y);
    if(xx!=yy)
    {
        f[xx]=yy;
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int s,n;
        scanf("%d%d",&s,&n);
        for(int i=0;i<n;i++)f[i]=i;
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&x[i],&y[i]);
        }
        int cont=0;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                a[cont].x=i;
                a[cont].y=j;
                a[cont++].w=dis(i,j);
            }
        }
        int cont2=0;
        sort(a,a+cont,cmp);
        for(int i=0;i<cont;i++)
        {
            if(find(a[i].x)!=find(a[i].y))
            {
                ans[cont2++]=a[i].w;
                merge(a[i].x,a[i].y);
            }
        }
        printf("%.2f\n",ans[cont2-s]);
    }
}