本人第一次看题,有点懵,不知道这道题是要求什么.然后看了一下算法标签,最小生成树,再一看题,好像是那么回事.
本题其实就是一个最小生成树的板子题.本题说可以装S个卫星电话,而我们知道要将n个点连成一棵树需要n-1条边.那么实际上我们求的就是这n-1条边中第s+1大的边.所以我们只需要跑一遍最小生成树,知道连了s+1条边的时候就行了.(本蒟蒻用的是Kruskal)
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cmath> 5 6 using namespace std; 7 8 int fa[100001],a[100001],b[100001],s,p,n,k; 9 double ans; 10 struct kkk { 11 double x,y,z; 12 }e[1000001]; 13 14 bool cmp(kkk a,kkk b) { 15 return a.z < b.z; 16 } 17 18 int find_father(int x) { 19 if(fa[x] == x) return x; 20 else return fa[x] = find_father(fa[x]); 21 } 22 23 int main() 24 { 25 scanf("%d%d",&s,&p); 26 for(int i = 1;i <= p; i++) { 27 scanf("%d%d",&a[i],&b[i]); 28 for(int j = 1;j < i; j++) { 29 n++; 30 e[n].z = sqrt((a[i] - a[j]) * (a[i] - a[j]) + (b[i] - b[j]) * (b[i] - b[j])); 31 //运用勾股定理求当前点到其它点的距离(应该都知道勾股定理吧) 32 e[n].x = i; 33 e[n].y = j; 34 } 35 } 36 for(int i = 1;i <= p; i++) 37 fa[i] = i; 38 sort(e+1,e+n+1,cmp); 39 for(int i = 1;i <= n; i++) { 40 int a = find_father(e[i].x); 41 int b = find_father(e[i].y); 42 if(a != b) { 43 fa[a] = b; 44 ans = e[i].z; 45 k++; 46 if(k >= p - s) { 47 printf("%.2lf",ans); 48 return 0; 49 } 50 } 51 } 52 return 0; 53 }
原文：https://www.cnblogs.com/lipeiyi520/p/11286104.html