一道水题，但得把这道题对应上最小生成树模型。

把整个问题看做一个完全图，村庄就是点， 图上两点之间的边的权值，就是两个村庄 的直线距离。

只需在该图上求最小生成树，d 的最小值即为 第 K  长边！

因为：最小生成树中的最长k-1条长边都去掉 后，正好将原树分成了k 个连通分支，在每 个连通分支上摆一个卫星设备即可

 

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6  7 struct point{ 8     int x,y; 9     point(int x1=0,int y1=0,int i1=0): x(x1),y(y1) {} 10 }points[505];11 12 struct edge{13     int u,v;14     double dis;15     edge(int u1=0,int v1=0,double d1=0): u(u1),v(v1),dis(d1) {}16     bool operator < (const edge n1) const{17         return dis
         
          >t;45     while(t--){46         top=0;47         int s,p; cin>>s>>p;48         for(int i=1;i<=p;i++){49             int x,y; cin>>x>>y;50             points[i]=point(x,y);51         }52         53         for(int i=1;i<=p;i++){54             for(int j=i+1;j<=p;j++){55                 edges[++top]=edge( i,j,find_dis(points[i],points[j]) );56             }57         }58         sort(edges+1,edges+1+top);59 60         //s个satellite省掉s-1个边，找到第s大的边 61         for(int i=1;i<=p;i++) parent[i]=i;62         63         int cnt=0;64         for(int i=1;i<=top;i++){65             int u = edges[i].u;66             int v = edges[i].v;67             if( merge(u,v) ) cnt++;68             //cnt是已经找到了多少条边69             if(cnt==p-s) { cout<
          
           <
           
            <
            
             <