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

作者: wjyyy 分类: 二分,并查集,快速排序,生成树,解题报告 发布时间: 2018-07-05 19:24

点击量:31

 

 

题目描述

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

 

不过好消息是,聪聪得到了一份荒岛的地图。地图上标注了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;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */