题解 P4047 【[JSOI2010]部落划分】 并查集+二分答案

2018-07-05 19:33:49


到博客食用更加优雅优秀

解法:

我的第一思路是二分答案检验,把某个距离以内的划分为同一个部落,检查是否被划分为k个部落。如果超过k个,则范围扩大,如果不超过k个(含k个),则范围缩小。因为题目要求分出k个部落,使两两部落间最小的距离最大。而同时,当部落多了应当控制距离增大,当部落少了控制距离减小。因此是有单调性的。(一开始并查集写错只有70分吓得我打了好长时间的对拍)

二分答案过程:

检查以mid为距离,枚举各个点,与点i的距离比mid小的,则与i归为一个部落。因为部落的基准点不同,也就是一个点可以因为存在部落里一个点与之距离小于mid而被归为一个部落。因为把各个点拉进同一个部落的点可能不同,因此我们可以用并查集做到这一点。被归为一个部落的用并查集放在一起就可以了。

其他

题解里其他同学做的是用生成树来做的,就是把所有点两两互连,当做一个有$\frac{n(n-1)}2$条边的稠密图,来做最小生成树,每一个点进来就减少一个连通块,最后一个使得连通块个数减为k的边即为所求。这样在某些情况会比二分答案更优,但在稠密图用二分答案比用kruscal在时间和空间上都稍微优一些 :) 。不过比较难想,细节颇多。

tips:二分平方最后开根可能精度更有保证,这个题保留2位小数就无所谓了&& 发现题目图片原来有彩蛋『JSOI』啊

Code:

#include<cstdio>
#include<cstring>
#include<cmath>
#define eps 1e-4
int c[10100],n,m;
int x[1010],y[1010];
int my_find(int x)
{
    if(c[x]==x)
        return x;
    return c[x]=my_find(c[x]);
}
bool check(double ans)
{
    for(int i=1;i<=n;i++)
        c[i]=i;
    int cnt=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if((x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i])<=ans)//暂时不开根号
                c[my_find(i)]=my_find(j);
    for(int i=1;i<=n;i++)
        if(my_find(i)==i)
            cnt++;
    if(cnt<m)//框多了
        return false;
    return true;
}
int main()
{
    double mx=0.0,my=0.0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x[i],&y[i]);
        mx=mx>x[i]?mx:x[i];//减小二分上界(其实没必要)
        my=my>y[i]?my:y[i];
    }
    //二分平方,保证精度(其实也没必要)
    double l=0.0,r=mx*mx+my*my,mid;
    while(r-l>eps)
    {
        mid=(l+r)/2.0;
        if(check(mid))
            l=mid;
        else
            r=mid;
    }
    printf("%.2lf\n",sqrt(l));
    return 0;
}