BZOJ 1821: [JSOI2010]Group 部落划分 Group

正文索引 [隐藏]

Description
Input
Output
Sample Input
Sample Output
题解
代码

Description

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

Input

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

Output

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

Sample Input

4 2
0 0
0 1
1 1
1 0

Sample Output

1.00

题解

稍微脑补一下就是最小生成树辣！Orz我竟然求距离忘记了Sqrt、、、、、

代码

/*Author:WNJXYK*/
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int Maxn=1000+5;
struct Point{
    double x,y;
    Point(){}
    Point(double x0,double y0):x(x0),y(y0){}
};
Point p[Maxn];
struct Edge{
    int x,y;
    double dist;
    inline double sqr(double x){
        return x*x;
    }
    inline double getDist(int x,int y){
        return sqrt(sqr(p[x].x-p[y].x)+sqr(p[x].y-p[y].y));
    }
    Edge(){}
    Edge(int x0,int y0){
        x=x0;y=y0;
        dist=getDist(x,y);
    }
};
Edge e[Maxn*Maxn];
inline bool cmp(Edge a,Edge b){
    if (a.dist<b.dist) return true;
    return false;
}
int Father[Maxn];
inline void initFather(){
    for (int i=0;i<Maxn;i++) Father[i]=i;
}
inline int getFather(int x){
    return Father[x]=Father[x]==x?x:getFather(Father[x]);
}
inline void mergeFather(int x,int y){
    int lx=getFather(x),ly=getFather(y);
    if (lx==ly) return;
    if (lx<ly){
        Father[ly]=lx;
    }else{
        Father[lx]=ly;
    }
}
int n,k;
int cnts=0;
int main(){
    initFather();
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        p[i]=Point(x,y);
    }
    for (int i=1;i<n;i++){
        for (int j=i+1;j<=n;j++){
            e[++cnts]=Edge(i,j);
        }
    }
    sort(e+1,e+cnts+1,cmp);
    int lim=cnts;
    cnts=n;
    for (int i=1;i<=lim;i++){
        if (getFather(e[i].x)!=getFather(e[i].y)){
            if (cnts>k){
                mergeFather(e[i].y,e[i].x);
                cnts--;
            }else{
                printf("%.2lfn",e[i].dist);
                return 0;
            }
        }
    }
    printf("0.00n");
    return 0;
}

/*Author:WNJXYK*/

#include<cstdio>

#include<cmath>

#include<algorithm>

using namespace std;

const int Maxn=1000+5;

struct Point{

double x,y;

Point(){}

Point(double x0,double y0):x(x0),y(y0){}

};

Point p[Maxn];

struct Edge{

int x,y;

double dist;

inline double sqr(double x){

return x*x;

}

inline double getDist(int x,int y){

return sqrt(sqr(p[x].x-p[y].x)+sqr(p[x].y-p[y].y));

}

Edge(){}

Edge(int x0,int y0){

x=x0;y=y0;

dist=getDist(x,y);

}

};

Edge e[Maxn*Maxn];

inline bool cmp(Edge a,Edge b){

if (a.dist<b.dist) return true;

return false;

}

int Father[Maxn];

inline void initFather(){

for (int i=0;i<Maxn;i++) Father[i]=i;

}

inline int getFather(int x){

return Father[x]=Father[x]==x?x:getFather(Father[x]);

}

inline void mergeFather(int x,int y){

int lx=getFather(x),ly=getFather(y);

if (lx==ly) return;

if (lx<ly){

Father[ly]=lx;

}else{

Father[lx]=ly;

}

int n,k;

int cnts=0;

int main(){

initFather();

scanf("%d%d",&n,&k);

for (int i=1;i<=n;i++){

int x,y;

scanf("%d%d",&x,&y);

p[i]=Point(x,y);

}

for (int i=1;i<n;i++){

for (int j=i+1;j<=n;j++){

e[++cnts]=Edge(i,j);

}

sort(e+1,e+cnts+1,cmp);

int lim=cnts;

cnts=n;

for (int i=1;i<=lim;i++){

if (getFather(e[i].x)!=getFather(e[i].y)){

if (cnts>k){

mergeFather(e[i].y,e[i].x);

cnts--;

}else{

printf("%.2lfn",e[i].dist);

return 0;

}

printf("0.00n");

return 0;

}

一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

WNJXYKの博客

喂你脚下有坑