题目链接：
http://poj.org/problem?id=2349
题目大意：
有n个警戒部队，现在要把这n个警戒部队编入一个通信网络，
有两种方式链接警戒部队：1,用卫星信道可以链接无穷远的部队.
2,用信号收发器可以链接周围d米以内的部队.
现在有s个卫星信道，问d最小是多少时能连接全部的警戒部队？
解题思路：
我是用求最小生成树，记录路径长度，对路径长度排序后，第k长的边就是答案，
但是队友是用最小k度限制生成树，因为我的方法它证明不了，也推翻不了~~~~，
最后我下去仔细想了想反证法还是可以证明的。
证明：
假设：先假设最小生成树的第k大边不是最优解。
证：现在有一MST，我从中删除了一条第k大的边s，则MST变成了两个联通分支，根据假设存在一条s'<s,可以使两个联通分支连起来变成联通树MST'，因为s'<s，则MST'<MST，可得出假设不成立！！！！
#include <cmath>
#include <string>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std; const int maxn = ;
const int INF = 0x3f3f3f3f;
const double Exp = 1e-; struct point
{
int x, y;
int length(point a)
{
return (a.x - x)*(a.x - x) + (a.y - y)*(a.y - y);
}
}; int cost[maxn+][maxn+], lowc[maxn+];
int vis[maxn+], num[maxn+]; void init ()
{
for (int i=; i<maxn+; i++)
for (int j=; j<maxn; j++)
cost[i][j] = INF;
}
int prim (int n)
{
int i, j;
memset (vis, , sizeof(vis));
vis[] = ;
for (i=; i<n; i++)
lowc[i] = cost[][i];
for (i=; i<n; i++)
{
int p, mini = INF;
for (j=; j<n; j++)
if (!vis[j] && lowc[j] < mini)
{
p = j;
mini = lowc[j];
}
vis[p] = ;
for (j=; j<n; j++)
{
if (!vis[j])
lowc[j] = min(lowc[j], cost[p][j]);
}
}
} int main ()
{
int n, s, p;
point P[maxn + ];
scanf ("%d", &n);
while (n --)
{
scanf ("%d %d", &s, &p);
for (int i=; i<p; i++)
{
scanf ("%d %d", &P[i].x, &P[i].y);
for (int j=; j<i; j++)
cost[i][j] = cost[j][i] = P[i].length(P[j]);
}
prim (p);
sort (lowc, lowc+p, greater<int>());
printf ("%.2f\n", sqrt(lowc[s-]));
}
return ;
}