洛谷P1991 无线通讯网

 1 /*
 2 性质：一个树里，删掉n条边一定出现n+1个连通块
 3 若删去无向连通图中所有权值大于m的边，原图被分割成k个连通块，则最小生成树也被分割成k个联通块 
 4 */ 
 5 #include<bits/stdc++.h>
 6 using namespace std;
 7 const int maxn=505;
 8 const int maxm=250005;
 9 struct node{int cnt,fa;}f[maxn];
10 int find(int x){return f[x].fa==x?x:f[x].fa=find(f[x].fa);}
11 void Union(int x,int y)
12 {
13     x=find(x),y=find(y);if(x==y) return;
14     if(f[x].cnt<=f[y].cnt) {f[x].fa=y;f[y].cnt+=f[x].cnt;}
15     else {f[y].fa=x;f[x].cnt+=f[y].cnt;}
16 }
17 int s,p,m,tot;
18 struct edge{int x,y;double dis;}e[maxm],t[maxm];
19 struct point{int x,y;}d[maxn];
20 inline bool cmp(const edge &a,const edge &b){return a.dis<b.dis;}
21 double dis(const point &x,const point &y){return sqrt((x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y));}
22 int main()
23 {
24     scanf("%d%d",&s,&p);
25     for(int i=1;i<=p;++i) f[i].fa=i,f[i].cnt=1;
26     for(int i=1;i<=p;++i) scanf("%d%d",&d[i].x,&d[i].y);
27     for(int i=1;i<=p;++i)
28         for(int j=1;j<i;++j)
29             e[++m].x=i,e[m].y=j,e[m].dis=dis(d[i],d[j]);
30     sort(e+1,e+1+m,cmp);
31     for(int i=1;i<=m;++i)
32     {
33         if(f[find(1)].cnt==p) break;
34         if(find(e[i].x)!=find(e[i].y)) Union(e[i].x,e[i].y),t[++tot]=e[i];
35     }
36     printf("%.2lf",t[tot-s+1].dis);
37     return 0;
38 }