题意：
有许多基地，每个基地都有两种收发信号的方式，一种是通过无线电收发机，另一种是通过卫星。两个基地之间可以通过卫星交流不管它们相距多远；但是通过无线电交流，就要求它们的距离不超过D。为了方便布置，节省成本，每个基地的无线电交流的最大距离都相等。给出基地的位置和卫星的数量，求出D，保证两个基地之间至少一个交流路径。
思路：
求出MST，保证了两点之间有路径，然后按照从大到小的顺序给在生成树中的边排序，将卫星安排给权值大的边，保证D尽可能小。s个卫星可以安排给s-1条边（s个点），所以第s条边的权值就是所求。克鲁斯卡尔算法，复杂度mlog(m)。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std; const int N = ; struct edge
{
int x,y;
double cost; edge(int a,int b,double c)
{
x = a;
y = b;
cost = c;
}
}; int px[N],py[N];
int par[N]; vector<edge> es;
vector<double> vd; double cal(int i,int j)
{
double x2 = (px[i] - px[j]) * (px[i] - px[j]);
double y2 = (py[i] - py[j]) * (py[i] - py[j]); return sqrt(x2 + y2);
} bool cmp(edge a,edge b)
{
return a.cost < b.cost;
} int fin(int x)
{
if (x == par[x]) return x;
else return par[x] = fin(par[x]);
} void unit(int x,int y)
{
x = fin(x);
y = fin(y); if (x == y) return; par[x] = y;
} bool comp(double a,double b)
{
return a > b;
} int main()
{
int t; scanf("%d",&t); while (t--)
{
int s,n; es.clear(); vd.clear(); scanf("%d%d",&s,&n); for (int i = ;i <= n;i++) par[i] = i; for (int i = ;i < n;i++)
{
scanf("%d%d",&px[i],&py[i]);
} for (int i = ;i < n;i++)
{
for (int j = i + ;j < n;j++)
{
double len = cal(i,j); es.push_back(edge(i,j,len));
}
} sort(es.begin(),es.end(),cmp); for (int i = ;i < es.size();i++)
{
int x = es[i].x,y = es[i].y; if (fin(x) == fin(y)) continue; unit(x,y); vd.push_back(es[i].cost);
} sort(vd.begin(),vd.end(),comp); double ans = ; printf("%.2f\n",vd[s-]);
} return ;
}