「BZOJ1821」[JSOI2010] Group 部落划分

灰太狼 2022-01-05 12:21 384阅读 0赞

[problem][]

# Description #

聪聪研究发现，荒岛野人总是过着群居的生活，但是，并不是整个荒岛上的所有野人都属于同一个部落，野人们总是拉帮结派形成属于自己的部落，不同的部落之间则经常发生争斗。只是，这一切都成为谜团了——聪聪根本就不知道部落究竟是如何分布的。 不过好消息是，聪聪得到了一份荒岛的地图。地图上标注了N个野人居住的地点（可以看作是平面上的坐标）。我们知道，同一个部落的野人总是生活在附近。我们把两个部落的距离，定义为部落中距离最近的那两个居住点的距离。聪聪还获得了一个有意义的信息——这些野人总共被分为了K个部落！这真是个好消息。聪聪希望从这些信息里挖掘出所有部落的详细信息。他正在尝试这样一种算法： 对于任意一种部落划分的方法，都能够求出两个部落之间的距离，聪聪希望求出一种部落划分的方法，使靠得最近的两个部落尽可能远离。 例如，下面的左图表示了一个好的划分，而右图则不是。请你编程帮助聪聪解决这个难题。

# Input #

第一行包含两个整数N和K(1< = N < = 1000,1< K < = N)，分别代表了野人居住点的数量和部落的数量。  
接下来N行，每行包含两个正整数x,y，描述了一个居住点的坐标(0 < =x, y < =10000)

# Output #

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

# Sample Input #

4 2
    0 0
    0 1
    1 1
    1 0

# Sample Output #

1.00

# Solution #

有点像Kruskal

首先\\(n^2\\)对点两两建边，边权就是距离

然后二分答案，二分出最大的最小距离\\(ans\\)

对于两个点，如果它的距离小于\\(ans\\)，那么它们一定在同一个集合中。如果最终划分出的集合数量小于\\(k\\)则为非法情况

如果划分出的集合数量大于\\(k\\)，那么我们可以随意合并若干个不同的集合使得数量回到\\(k\\)，而不会对答案产生影响

# Code #

怕有精度误差，所以我在输出时才对距离开方

#include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #include <iostream>
    #define maxn 1005
    using namespace std;
    typedef long long ll;
    
    template <typename T>inline void read(T &t)
    {
        t=0;char c=getchar();int f=0;
        while(!isdigit(c)){f|=c=='-';c=getchar();}
        while(isdigit(c)){t=t*10+c-'0';c=getchar();}
        if(f)t=-t;
    }
    
    const double eps=1e-4;
    int n,K;
    double x[maxn],y[maxn];
    int prt[maxn];
    
    int ecnt;
    struct edge
    {
        int u,v;
        double w;
        edge(int x=0,int y=0,double z=0)
        {
            u=x,v=y,w=z;
        };
    }g[maxn*maxn/2];
    
    double dist(const int &a,const int &b)
    {
        return (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]);
    }
    
    bool cmp(const edge &a,const edge &b)
    {
        return a.w<b.w;
    }
    
    int getroot(int x)
    {
        return prt[x]==x?x:prt[x]=getroot(prt[x]);
    }
    
    bool Check(double ans)
    {
        for(register int i=1;i<=n;++i)
            prt[i]=i;
        int cnt=n;
        for(register int i=1;i<=ecnt && g[i].w<=ans;++i)
        {
            int r1=getroot(g[i].u),r2=getroot(g[i].v);
            if(r1!=r2)
            {
                --cnt;
                prt[r2]=r1;
            }
            if(cnt<K)
                return false;
        }
        return true;
    }
    
    int main()
    {
        read(n),read(K);
        for(register int i=1;i<=n;++i)
            read(x[i]),read(y[i]);
        for(register int i=1;i<=n;++i)
            for(register int j=i+1;j<=n;++j)
                g[++ecnt]=edge(i,j,dist(i,j));
        sort(g+1,g+ecnt+1,cmp);
        register double l=0,r=10000*10000;
        while(r-l>eps)
        {
            double mid=(l+r)/2;
            if(Check(mid))
                l=mid;
            else
                r=mid;
        }
        printf("%.2f",sqrt(l));
        return 0;
    }

转载于:https://www.cnblogs.com/lizbaka/p/10293134.html

[problem]: https://www.lydsy.com/JudgeOnline/problem.php?id=1821