[JSOI2010]部落划分

题面

link

solution1

这道题提供两种解题思路

解题思路1：

我们枚举计算点两两之间的距离。

然后我们从小到大考虑每一个距离。

如果我们想让部落之间的最短距离最大,就要尽可能让当前的边连接的两个点在同一个部落中。

因此我们记录剩余的部落数量,每次把最短的,连接两个部落的边连接的两个部落合并成一个,直到剩余部落数量为k。

然后剩下的边权最小的连接两个部落的边长就是答案了。

就是类似于Kruskal的过程。

code1

AC代码如下

#include<bits/stdc++.h>
using namespace std;
const double _=1e-10;
struct point{
    int x,y;
    double operator-(const point&b)const{
        return sqrt(1.0*(x-b.x)*(x-b.x)+1.0*(y-b.y)*(y-b.y));
    }
}p[1010];
struct edge{
    int u,v;
    double w;
}e[500010];
int n,k,sz,f[1010],tot;
bool cmp(edge x,edge y){
    return y.w-x.w>_;
}
int getf(int x){
    return f[x]==x?x:f[x]=getf(f[x]);
}
void Merge(int x,int y){
    getf(x),getf(y);
    f[f[x]]=f[y];
}

int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i){
        scanf("%d%d",&p[i].x,&p[i].y);
        for(int j=1;j<i;++j)e[++sz]=(edge){i,j,p[i]-p[j]};
    }
    sort(e+1,e+sz+1,cmp);
    for(int i=1;i<=n;++i)f[i]=i;
    tot=n;
    for(int i=1;i<=sz;++i){
        if(getf(e[i].u)!=getf(e[i].v)){
            if(tot==k)printf("%.2lf",e[i].w),exit(0);
            else Merge(e[i].u,e[i].v),--tot;
        }
    }
    return 0;
}

solution2

解题思路2：

预处理出野人两两之间的距离，二分部落之间的最小距离，用并查集维护集合。

如果两个野人之间的距离比当前答案小，则将其分在同一个集合中。

最后统计一共分了几个部落，如果分的部落数量大于等于k，那再让答案变大，最后注意一下精度问题。

code2

AC代码如下：

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=1005;
struct cc{
    double x,y;
}num[maxn];
double a[maxn][maxn];
int f[maxn];
int find(int w)
{
    if(f[w]!=w)
        f[w]=find(f[w]);
    return f[w];
}
int n,k;
bool check(double mid)
{
    for(int i=1;i<=n;i++)
        f[i]=i;

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            if(a[i][j]<=mid)
            {
                if(find(i)!=find(j))
                    f[find(i)]=find(j);
            }
    }
    int tot=0;
    for(int i=1;i<=n;i++)
        if(f[i]==i)
            tot++;

    if(tot>=k)
        return 1;
    else
        return 0;
}
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        scanf("%lf%lf",&num[i].x,&num[i].y);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            a[i][j]=sqrt((num[i].x-num[j].x)*(num[i].x-num[j].x)+(num[i].y-num[j].y)*(num[i].y-num[j].y));

    double l=0,r=1000001;
    double ans=0;
    while(r-l>=0.0001)
    {
        double mid=(l+r)/2;
        if(check(mid))
        {
            l=mid+0.001;
            ans=max(ans,mid);
        }
        else
        {
            r=mid-0.001;
        }
    }
    printf("%.2lf",ans);
    return 0;
}