bzoj 1821: [JSOI2010]Group 部落划分 Group
2024-10-18 18:26:12
#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个块。
最新文章
- JavaScript (jquery) 数组去重的算法探讨
- Qt学习笔记网络(一)
- JQuery实现click事件绑定与触发方法分析
- mysql默认字符集修改
- unity Android 打包后读取 xml 文件
- zimbra启用SMTP认证并绑定认证登录和发件人
- 用js实现图片的无缝滚动效果
- 二、添加 Insert into
- Auto Layout Masonry
- 毕业设计——Django邮件发送功能实现及问题记录
- 如何在MongoDB设计存储你的数据(JSON化)?
- innoDB锁小结
- 自适应阈值二值化之最大类间方差法(大津法,OTSU)
- 未能找到temp\select2.cur的一部分
- zcat,zgrep用法
- js判断是否手机自动跳转移动端
- 运行代码后出现Process finished with exit code 0是为什么?
- Python性能分析指南(未完成)
- 01、Windows Phone 套接字(Socket)实战之交互设计
- ANE报错fix:Could not generate timestamp: Connection reset.
热门文章
- iOS 推送消息长度
- [转载] what&#39;s goole mock
- 1503 - A PRIMARY KEY must include all columns in the table&#39;s partitioning function
- 在SSH框架中使用Spring的好处
- u盘在电脑读不出来,但别的可以读,别的u盘在我电脑又可以识别怎么回事?
- 【转载】【Oracle 11gR2】db_install.rsp详解
- 【图像处理Matlab】2 灰度变换 imadjust stretchlim
- 检测访问网页的浏览器呈现引擎、平台、Windows操作系统、移动设备和游戏系统
- WEB网页插件 如何实现 选择上传图片路径 【高级问题】
- C++模板特化