洛谷 P1991 无线通讯网

题目传送门

解题思路:

本人第一次看题,有点懵,不知道这道题是要求什么.然后看了一下算法标签,最小生成树,再一看题,好像是那么回事.

本题其实就是一个最小生成树的板子题.本题说可以装S个卫星电话,而我们知道要将n个点连成一棵树需要n-1条边.那么实际上我们求的就是这n-1条边中第s+1大的边.所以我们只需要跑一遍最小生成树,知道连了s+1条边的时候就行了.(本蒟蒻用的是Kruskal)

AC代码:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath> 

using namespace std;

int fa[100001],a[100001],b[100001],s,p,n,k;
double ans;
struct kkk {
    double x,y,z;
}e[1000001]; 

bool cmp(kkk a,kkk b) {
    return a.z < b.z;
}

int find_father(int x) {
    if(fa[x] == x) return x;
    else return fa[x] = find_father(fa[x]);
}

int main()
{
    scanf("%d%d",&s,&p);
    for(int i = 1;i <= p; i++) {
        scanf("%d%d",&a[i],&b[i]);
        for(int j = 1;j < i; j++) {
            n++;
            e[n].z = sqrt((a[i] - a[j]) * (a[i] - a[j]) + (b[i] - b[j]) * (b[i] - b[j]));
            //运用勾股定理求当前点到其它点的距离(应该都知道勾股定理吧) 
            e[n].x = i;
            e[n].y = j;
        }
    }
    for(int i = 1;i <= p; i++) 
        fa[i] = i;
    sort(e+1,e+n+1,cmp);
    for(int i = 1;i <= n; i++) {
        int a = find_father(e[i].x); 
        int b = find_father(e[i].y);
        if(a != b) {
            fa[a] = b;
            ans = e[i].z;
            k++;
            if(k >= p - s) {
                printf("%.2lf",ans);
                return 0;
            }
        }
    }
    return 0;
}