题目链接：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条边里最长的边的距离。
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<math.h> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 const int N=1e3+5; 8 ?9 struct node2{10 ????int x,y;11 }a[N];12 13 struct node{14 ????int x,y;15 ????double dis;16 ????node(){}17 ????node(int x,int y,double dis){18 ????????this->x=x;19 ????????this->y=y;20 ????????this->dis=dis;21 ????}22 ????bool operator <(const node &b)const{23 ????????return dis<b.dis;24 ????}25 }edge[N*N];26 int root[N];27 28 int find(int x){29 ????return root[x]==x?x:root[x]=find(root[x]);30 }31 32 int main(){33 ????int t;34 ????scanf("%d",&t);35 ????while(t--){36 ????????int s,n;37 ????????scanf("%d%d",&s,&n);38 ????????for(int i=1;i<=n;i++){39 ????????????scanf("%d%d",&a[i].x,&a[i].y);40 ????????????root[i]=i;41 ????????}42 ????????int cnt=0;43 ????????for(int i=1;i<=n;i++){44 ????????????for(int j=i+1;j<=n;j++){45 ????????????????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));46 ????????????????edge[++cnt]=node(i,j,dis);47 ????????????}48 ????????}49 ????????sort(edge+1,edge+1+cnt);50 ????????51 ????????int ???edge_num=0;52 ????????double ans;53 ????????for(int i=1;i<=cnt;i++){54 ????????????int x=find(edge[i].x);55 ????????????int y=find(edge[i].y);56 ????????????if(x!=y){57 ????????????????edge_num++;58 ????????????????root[x]=y;59 ????????????????//从最小生成树中的n-1条边，去掉最大的s-1条边（因为有s个卫星站，相当于s个点，则s-1条边）60 ????????????????//剩下的n-s条边中，最大的边长即为所求61 ????????????????if(edge_num==n-s){62 ????????????????????ans=edge[i].dis;63 ????????????????????break;64 ????????????????}65 ????????????}66 ????????}67 ????????printf("%.2f\n",ans);68 ????}69 ????return 0;70 }POJ 2349 Arctic Network(最下生成树+求第k大边)
原文地址：http://www.cnblogs.com/fu3638/p/7899911.html