这题主要考察对“卫星电话”的理解，k个卫星电话相当于可以让k个联通块保持联通，因此我们只需要让原图连成k个联通块，然后给每个联通块的任意一个节点发一部卫星电话即可。因此我们需要连n-k条边，特别地，当k=0时只需要连n-1条边
一定要好好读题！！！题目要求求边权的最大值，毒瘤样例求最大值，最小值，边权和，直接输出均可拿到17分，建议同学们自己出样例，防止被毒瘤样例搞废！！！
附赠SZM考场检查的样例：
4 2
0 100
0 300
0 600
150 750
输出：212.13
参考代码如下：
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cmath> 5 #define N 1000001 6 using namespace std; 7 int read() 8 { 9 int x=0,f=1;char ch=getchar(); 10 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 11 while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();} 12 return x*f; 13 } 14 int n,k,sum,parent[N]; 15 double x[N],y[N]; 16 double weight; 17 struct node 18 { 19 int u,v; 20 double w; 21 }f[5000005]; 22 bool cmp(node a,node b) 23 { 24 return a.w<b.w; 25 } 26 int find(int x) 27 { 28 if(parent[x]==x)return x; 29 return parent[x]=find(parent[x]); 30 } 31 void Union(int u,int v) 32 { 33 int U=find(u),V=find(v); 34 if(U==V)return; 35 parent[U]=V; 36 } 37 int main() 38 { 39 cin>>n>>k; 40 for(int i=1;i<=n;i++)parent[i]=i; 41 for(int i=1;i<=n;i++) 42 { 43 cin>>x[i]>>y[i]; 44 //x[i]=read();y[i]=read(); 45 } 46 for(int i=1;i<=n;i++) 47 { 48 for(int j=1;j<i;j++) 49 { 50 f[++sum].u=i;f[sum].v=j;f[sum].w=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); 51 } 52 } 53 sort(f+1,f+1+sum,cmp); 54 int num=0; 55 for(int i=1;i<=sum;i++) 56 { 57 int u=f[i].u,v=f[i].v; 58 59 if(find(u)!=find(v)) 60 { 61 Union(u,v); 62 weight=max(weight,f[i].w); 63 num++; 64 } 65 if(num==n-k)break; 66 } 67 printf("%.2lf",weight); 68 return 0; 69 }