题目链接：http://poj.org/problem?id=2349
题目大意：有n个前哨，和s个卫星通讯装置，任何两个装了卫星通讯装置的前哨都可以通过卫星进行通信，而不管他们的位置。 否则，只有两个前哨之间的距离不超过D，才能通过无线电进行通信。求出能使所有前哨都能直接或间接通信的最小的D。
解题思路：题目要求使所有前哨都能直接或间接通信，那么相当于使n个点相连，至少需要n-1条边。可以将n个点分为s个团，每个团内部时无限通信，团与团之间通过卫星通信。那么就相当于用s个卫星装置建立s-1条边，用无线电通信建立n-1-(s-1)==n-s条边，由于卫星通信是没有距离限制的那就可以选择最大的s-1条边，那D就是剩下n-s条边里最长的边的距离。
代码：
#include<iostream>
#include<cstdio>
#include<math.h>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e3+; struct node2{
int x,y;
}a[N]; struct node{
int x,y;
double dis;
node(){}
node(int x,int y,double dis){
this->x=x;
this->y=y;
this->dis=dis;
}
bool operator <(const node &b)const{
return dis<b.dis;
}
}edge[N*N];
int root[N]; int find(int x){
return root[x]==x?x:root[x]=find(root[x]);
} int main(){
int t;
scanf("%d",&t);
while(t--){
int s,n;
scanf("%d%d",&s,&n);
for(int i=;i<=n;i++){
scanf("%d%d",&a[i].x,&a[i].y);
root[i]=i;
}
int cnt=;
for(int i=;i<=n;i++){
for(int j=i+;j<=n;j++){
double dis=sqrt(1.0*(a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y));
edge[++cnt]=node(i,j,dis);
}
}
sort(edge+,edge++cnt); int edge_num=;
double ans;
for(int i=;i<=cnt;i++){
int x=find(edge[i].x);
int y=find(edge[i].y);
if(x!=y){
edge_num++;
root[x]=y;
//从最小生成树中的n-1条边，去掉最大的s-1条边（因为有s个卫星站，相当于s个点，则s-1条边）
//剩下的n-s条边中，最大的边长即为所求
if(edge_num==n-s){
ans=edge[i].dis;
break;
}
}
}
printf("%.2f\n",ans);
}
return ;
}