BZOJ1821:[JSOI2010]Group 部落划分 Group 二分+并查集

思路:

我保证这是一种奇葩算法.

我们二分答案,那么问题就转化为若任意两个部落之间的距离\(\leq{l}\),是否能够划分为为\(k\)组.

我们能发现以下性质:若能够划分为\(k'\)组,且满足\(k'>k\),则必定能够划分为\(k\)组.原因是我们可以合并一些块,那么部落之间距离的最小值必然不会减少.

因此我们只需考虑对于一个给定的\(l\),最多能够划分为几组.

考虑两个点,若两点距离\(\leq{l}\),那么必定划分在一组中.那么现在有若干个连通块,不同连通块之间的所有点的距离均\(>l\),显然当前连通块数就是我们要求的最大连通块数.

于是二分+并查集水.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
 
#define N 1010
int n,k,x[N],y[N],r[N];
 
inline void init(){for(int i=1;i<=n;++i)r[i]=i;}
inline int find(int x){int q=x,rq;for(;x!=r[x];x=r[x]);for(;q!=x;q=rq)rq=r[q],r[q]=x;return x;}
inline void merge(int x,int y){r[find(x)]=find(y);}
typedef double f2;
 
f2 dis(int a,int b){
    return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
 
 
int main(){
    scanf("%d%d",&n,&k);register int i,j;
    for(i=1;i<=n;++i)scanf("%d%d",&x[i],&y[i]);
     
    f2 Maxdis=0;
    for(i=1;i<=n;++i)for(j=i+1;j<=n;++j)Maxdis=max(Maxdis,dis(i,j));
     
    f2 L=0,R=Maxdis,mid;
    while(R-L>1e-4){
        mid=(L+R)*.5;
        init();
        for(i=1;i<=n;++i)for(j=i+1;j<=n;++j)if(dis(i,j)<=mid)merge(i,j);
         
        int cnt=0;for(i=1;i<=n;++i)cnt+=(i==find(i));
         
        if(cnt>=k)L=mid;else R=mid;
    }
     
    printf("%.2lf",L);
     
    return 0;
}