洛谷 P4047 [JSOI2010]部落划分 题解【二分答案】【生成树】【并查集】

点击量：446

目录

题目描述

聪聪研究发现，荒岛野人总是过着群居的生活，但是，并不是整个荒岛上的所有野人都属于同一个部落，野人们总是拉帮结派形成属于自己的部落，不同的部落之间则经常发生争斗。只是，这一切都成为谜团了——聪聪根本就不知道部落究竟是如何分布的。

 

不过好消息是，聪聪得到了一份荒岛的地图。地图上标注了N个野人居住的地点（可以看作是平面上的坐标）。我们知道，同一个部落的野人总是生活在附近。我们把两个部落的距离，定义为部落中距离最近的那两个居住点的距离。聪聪还获得了一个有意义的信息——这些野人总共被分为了K个部落！这真是个好消息。聪聪希望从这些信息里挖掘出所有部落的详细信息。他正在尝试这样一种算法：

 

对于任意一种部落划分的方法，都能够求出两个部落之间的距离，聪聪希望求出一种部落划分的方法，使靠得最近的两个部落尽可能远离。

 

例如，下面的左图表示了一个好的划分，而右图则不是。请你编程帮助聪聪解决这个难题。

输入输出格式

输入格式：

输入文件第一行包含两个整数N和K(1<=N<=1000,1<K<=N)，分别代表了野人居住点的数量和部落的数量。

 

接下来N行，每行包含两个整数x,y，描述了一个居住点的坐标(0<=x, y<=10000)。

 

输出格式：

输出一行，为最优划分时，最近的两个部落的距离，精确到小数点后两位。

 

输入输出样例

输入样例#1：

4 2

0 0

0 1

1 1

1 0

输出样例#1：

1.00

输入样例#2：

9 3

2 2

2 3

3 2

3 3

3 5

3 6

4 6

6 2

6 3

输出样例#2：

2.00

解法：

   我的第一思路是二分答案检验，把某个距离以内的划分为同一个部落，检查是否被划分为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;
}

Code：（Kruscal）

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
struct edge
{
    int x,y;
    int dis;
    edge(int x,int y,int dis)
    {
        this->x=x;
        this->y=y;
        this->dis=dis;
    }
    edge(){}
    friend bool operator <(edge a,edge b)
    {
        return a.dis<b.dis;
    }
}e[1010000];
int x[1010],y[1010];
int s[1010];
int my_find(int x)
{
    if(s[x]==x)
        return x;
    return s[x]=my_find(s[x]);
}
void my_union(int x,int y)
{
    s[my_find(y)]=my_find(x);
    return;
}
int main()
{
    int n,m,cnt=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        s[i]=i;
        scanf("%d%d",&x[i],&y[i]);
        for(int j=1;j<i;j++)
            e[++cnt]=edge(i,j,(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
    }
    std::sort(e+1,e+1+cnt);
    int Cnt=n,i;
    for(i=1;i<=cnt;i++)
        if(my_find(e[i].x)!=my_find(e[i].y))
        {
            my_union(e[i].x,e[i].y);
            Cnt--;
            if(Cnt==m-1)//不够了
                break;
        }
    printf("%.2lf\n",sqrt(e[i].dis));//保留最后一个距离
    return 0;
}