【JSOI2010】【BZOJ1821】部落划分（二分+并查集）

显然最近的两个部落的距离是有单调性的 因此可以二分

考虑check 我们遍历所有点 先把<=limit的点连起来 这样是肯定可以划分在一个部落里的 再用并查集维护一下

然后扫一遍 如果father[i]=i 说明就有一个部落

注意double

#include<bits/stdc++.h>
#define N 1005
#define eps 1e-6
using namespace std;
template<class T>
inline void read(T &x)
{
    x=0;
    static char ch=getchar();
    while(ch<'0'||ch>'9')   ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
}
int n,k;
double dis[N][N];
struct P
{
    double x,y;
}point[N];
inline double calc_dis(int i,int j)
{
    return sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y));
}
int father[N];
inline int getfather(int x)
{
    if(father[x]==x)    return x;
    father[x]=getfather(father[x]);
    return father[x];
}
inline bool check(double limit)
{
    for(int i=1;i<=n;i++)   father[i]=i;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)
        {
            if(dis[i][j]>limit) continue;
            int fa1=getfather(i),fa2=getfather(j);
            if(fa1!=fa2)    father[fa1]=fa2;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
        if(father[i]==i)    ans++;
    return ans>=k;
}
int main()
{
    read(n);    read(k);
    for(int i=1;i<=n;i++) read(point[i].x), read(point[i].y);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dis[i][j]=calc_dis(i,j); 
    double l=0,r=100000;
    while(l+eps<=r)
    {
        double m=(l+r)/2;
        if(check(m))    l=m;
        else r=m;   
    }
    cout<<fixed<<setprecision(2)<<l;
    return 0;
}

转载于:https://www.cnblogs.com/Patrickpwq/articles/9847659.html