poj2349:http://poj.org/problem?id=2349
题意：有卫星电台的城市之间可以任意联络。没有卫星电台的城市只能和距离小于等于D的城市联络。告诉你卫星电台的个数S，让你求最小的D.
题解： 生成最小生成树，去掉最长的S条边后，剩下最长的边就是D.也就是求最小生成树中第S+1长的边。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define INF 100000000.0
using namespace std;
int cas,x,y,top;
int n,s;
double lowcost[],ans[],g[][];
struct Node{
int x;
int y;
}node[];
double juli(Node a,Node b ){
return sqrt(((double)a.x-b.x)*(a.x-b.x)+((double)a.y-b.y)*(a.y-b.y));
}
void prim(int v0){
top=;
for(int i=;i<=n;i++){
lowcost[i]=g[v0][i];
}
lowcost[v0]=-;
for(int i=;i<n;i++){
double min=INF;
int v=-;
for(int j=;j<=n;j++){
if(lowcost[j]!=-&&lowcost[j]<min){
min=lowcost[j];
v=j;
}
}
if(v!=-){
ans[top++]=lowcost[v];
lowcost[v]=-;
for(int k=;k<=n;k++){
if(lowcost[k]!=-&&g[v][k]<lowcost[k]){
lowcost[k]=g[v][k];
}
}
}
}
}
void solve(){
sort(ans,ans+top);
printf("%.2f\n",ans[top-s]);
}
int main(){
scanf("%d",&cas);
while(cas--){
scanf("%d%d",&s,&n);
for(int i=;i<=n;i++){
scanf("%d %d",&node[i].x,&node[i].y);
}
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++){
g[i][j]=g[j][i]=juli(node[i],node[j]);
// printf("%.2f\n",g[i][j]);
}
for(int i=;i<=n;i++)
for(int j=;j<=n;j++){
if(i==j)g[i][j]=;
else if(g[i][j]==)g[i][j]=INF;
}
prim();
solve();
}
}