2489 - 北极网络
国家安全局希望把北极的数个前哨站用一个无线网络链接起来。为了建立网络，有两种不同的通讯技术可以使用，分别是无线电通信和卫星通信。每一个前哨站都拥有一个无线电收发器，部分前哨站额外拥有卫星通信器。
拥有卫星通信器的前哨站之间可以无视距离进行通信；而只有无线电收发器的前哨站则可以在不超过D的距离范围内进行通信，D的大小取决于收发器的功率大小。功率越高D值越大，不过消耗也就越多。出于设备购买与维护的考虑，所有前哨站的无线电收发器都是一致的，也就是所有收发器的D值都是一样的。
你的工作是确定无线电收发器所需的最小D值。
每一对前哨站之间都必须建立至少一条（直接或间接的）通信线路。
Input
数据的第一行是正整数N，代表数据的组数。
每一组测试数据的第一行为两个数S（1<=S<=100），代表卫星通信器的数量，还有P（S<P<=500），代表前哨站的数量。
其后P行，每行为一个前哨站的坐标（x，y）（x，y均为0到10000间的整数）。
Output
对于每一组测试数据，输出为一行，给出建立通信网络所需的最小的D值，精确到小数点后两位。
Examples
Input
1 2 4 0 100 0 300 0 600 150 750
Output
212.13
Solution C++
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #define INF 999999.0 using namespace std; struct Outpost{ int x, y; }O[501]; int cmp(double a, double b){ return a > b; } int s, p; double dist[501][501], d[501]; char vis[501]; void prim(){ int i, j, k, mini, minj; double min; vis[1] = mini = 1; for(i = 1; i <= p; i++){ min = INF; for(j = 1; j <= p; j++){ if(!vis[j]){ if(dist[mini][j] < d[j]){ d[j] = dist[mini][j]; } if(d[j] < min){ min = d[j]; minj = j; } } } mini = minj; vis[mini] = 1; } } int main(){ int k, i, j, x, y; scanf("%d", &k); while(k--){ scanf("%d%d", &s, &p); memset(vis, 0, sizeof(vis)); memset(O, 0, sizeof(O)); for(i = 1; i <= p; i++){ scanf("%d%d", &O[i].x, &O[i].y); d[i] = INF; } for(i = 1; i <= p; i++){ for(j = 1; j <= i; j++){ x = O[i].x-O[j].x; y = O[i].y-O[j].y; dist[i][j] = dist[j][i] = sqrt(x*x + y*y); } } prim(); sort(d+1, d+p+1); printf("%.2f\n", d[p-s]); } return 0; }