The Department of National Defence (DND) wishes to connect several northern outposts by a wireless network. Two different communication technologies are to be used in establishing the network: every outpost will have a radio transceiver and some outposts will in addition have a satellite channel. 
Any two outposts with a satellite channel can communicate via the satellite, regardless of their location. Otherwise, two outposts can communicate by radio only if the distance between them does not exceed D, which depends of the power of the transceivers. Higher power yields higher D but costs more. Due to purchasing and maintenance considerations, the transceivers at the outposts must be identical; that is, the value of D is the same for every pair of outposts.

Your job is to determine the minimum D required for the transceivers. There must be at least one communication path (direct or indirect) between every pair of outposts.

The first line of input contains N, the number of test cases. The first line of each test case contains 1 <= S <= 100, the number of satellite channels, and S < P <= 500, the number of outposts. P lines follow, giving the (x,y) coordinates of each outpost in km (coordinates are integers between 0 and 10,000).

For each case, output should consist of a single line giving the minimum D required to connect the network. Output should be specified to 2 decimal points.

1

2 4

0 100

0 300

0 600

150 750

212.13

题意简化：
　　个人觉得这道题最难的在于理解，简化以后的题意是：　　

代码及分析：

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

//n个卫星，m个基站

int n, m;

int x, y;

const int maxn = ;

const int INF = 0x3f3f3f3f;

int parent[maxn];

//有多少个边

int num;

//ans数组中存储的是升序排序的入树的边的权值

double ans[maxn];

struct point

{

    int x;

    int y;

} p[maxn];

struct ds

{

    int u;

    int v;

    double w;

} d[maxn * maxn + maxn];

double dist(const point& a, const point& b)

{

    return sqrt(1.0 * (a.x - b.x) * (a.x - b.x) +

                1.0 * (a.y - b.y) * (a.y - b.y));

}

bool cmp(const ds &a, const ds& b)

{

    return a.w < b.w;

}

//并查集中找到父节点的操作

int Find(int x)

{

    //递归？

    //parent[x] = Find(parent[x]);

    //return parent[x];

    //自己写的迭代

    int tmp = x;

    while(parent[tmp] != tmp)

    {

        tmp = parent[tmp];

    }

    return tmp;

}

void merge(int x, int y)

{

    int fa = Find(x);

    int fb = Find(y);

    if(fa != fb)

    {

        parent[fa] = fb;

    }

}

void init()

{

    scanf("%d%d",&n,&m);

    num = ;

    for(int i =  ; i < m ; i++)

    {

        scanf("%d%d",&p[i].x,&p[i].y);

    }

    for(int i = ; i < m ; i++)

        for(int j = i + ; j < m ; j++)

        {

            d[num].u = i;

            d[num].v = j;

            d[num++].w = dist(p[i],p[j]);

        }

    for(int i =  ; i <= m ; i++)

        parent[i] = i;

    //从小到大进行排序

    sort(d,d+num,cmp);

}

//最主要的代码：Kruskal

void kruskal()

{

    int cnt =  ;

    for(int i =  ; i < num ; i++)

    {

        int fa = Find(d[i].u);

        int fb = Find(d[i].v);

        if(fa != fb)

        {

            merge(d[i].u,d[i].v);

            ans[cnt++] = d[i].w;

        }

    }

     printf("%.2f\n",ans[cnt - n]);

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        init();

        kruskal();

    }

    return ;

}