题解 P1991 【无线通讯网】

· · 题解

{\color{orange}\text{欢迎拜访我这个蒟蒻的博客}}

P1991 【无线通讯网】

此题算法:二分+并查集

大致思路:

1. 输入点，算出二分D的平方(必定为整数)的边界。l=0，r为任意两点间的最长距离。

2. 二分。若两点间距离的平方<=mid就合并为一块。二分条件：块数是否<=s。

3. 最后得出整数答案l，\sqrt l就是答案。

以下是代码+注释

#include <bits/stdc++.h>
using namespace std;
#define f(v) (v)*(v)
const int N=510;
int s,p,xt,yt,l,r,mid,sum; //平方必定为整数
struct point{
    int x,y;
}P[N];
struct Un{ //并查集
    int f[N];
    void clear(int x){
        for(int i=1;i<=x;i++)
            f[i]=i;
    } int find(int x){
        if(f[x]==x) return x;
        return f[x]=find(f[x]);
    } void merge(int x,int y){
        x=find(x);
        y=find(y);
        f[y]=x;
    } bool same(int x,int y){
        return (find(x)==find(y));
    } 
}BCJ;
int dis(point a,point b){//距离
    return f(a.x-b.x)+f(a.y-b.y);
} int main(){
    scanf("%d%d",&s,&p);
    for(int i=1;i<=p;i++){
        scanf("%d%d",&xt,&yt);
        P[i]=(point){xt,yt};
    } for(int i=1;i<=p;i++)
        for(int j=i+1;j<=p;j++)
            r=max(dis(P[i],P[j]),r); //求出l和r
    while(l<r){
        mid=(l+r)>>1;
        BCJ.clear(p); sum=p;
        for(int i=1;i<=p;i++){
            for(int j=i+1;j<=p;j++){
                if(!BCJ.same(i,j)&&
                dis(P[i],P[j])<=mid){
                    BCJ.merge(i,j);
                    sum--; //合并
                }
            }
        } if(sum<=s)
            r=mid;
        else l=mid+1;
    } printf("%.2lf\n",sqrt(l)); //得出答案
    return 0;
}

为我点个赞吧，祝你名后挂金钩!

谢谢大家! !