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

 #include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#define M 1008
struct data
{
int a1,a2,d;
}q[M*M];
int x[M],y[M],n,k,cnt,fa[M],sum1;
bool cmp(data b1,data b2)
{
return b1.d<b2.d;
}
int zhao(int a1)
{
if(fa[a1]==a1)
return a1;
fa[a1]=zhao(fa[a1]);
return fa[a1];
}
using namespace std;
int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
scanf("%d%d",&x[i],&y[i]);
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
{
cnt++;
q[cnt].a1=i;
q[cnt].a2=j;
q[cnt].d=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
}
sort(q+,q+cnt+,cmp);
for(int i=;i<=n;i++)
fa[i]=i;
for(int i=;i<=cnt;i++)
{
int b1=zhao(q[i].a1),b2=zhao(q[i].a2);
if(b1!=b2)
{
n--;
fa[b1]=b2;
if(n<k)
{
printf("%.2lf\n",sqrt(q[i].d));
return ;
}
}
}
}

并查集,每次把最近的两个点合并,直到只有k个块。

上一篇:发布自己的pods到CocoaPods trunk 及问题记录


下一篇:hibernate---ID生成策略