bzoj 2429: [HAOI2006]聪明的猴子 (最小生成树)
2024-10-14 06:34:34
链接:https://www.lydsy.com/JudgeOnline/problem.php?id=2429
思路:就是找最小生成树最大的一条边,最小生成树的性质,最后加入的那条边就是最大的
实现代码:
#include<bits/stdc++.h>
using namespace std;
const int M = 1e6 + ;
struct node{
int u,v,w;
}e[M]; struct node1{
int x,y;
}v[M];
int f[M],a[M];
bool cmp(node a,node b){
return a.w < b.w;
} int Find(int x){
if(x == f[x]) return x;
return f[x] = Find(f[x]);
} int main()
{
int n,m,cnt = ;
cin>>n;
for(int i = ;i <= n;i ++){
cin>>a[i];
}
cin>>m;
for(int i = ;i <= m;i ++){
cin>>v[i].x>>v[i].y;
f[i] = i;
}
for(int i = ;i <= m;i ++){
for(int j = i+;j <= m;j ++){
e[++cnt].u = i; e[cnt].v = j;
e[cnt].w = (v[i].x-v[j].x)*(v[i].x-v[j].x)+(v[i].y-v[j].y)*(v[i].y-v[j].y);
}
}
sort(e+,e++cnt,cmp);
int mx = ,tot= ;
for(int i = ;i <= cnt;i ++){
int fx = Find(e[i].u),fy = Find(e[i].v);
if(fx != fy){
f[fy] = fx;
tot++;
if(tot == m-){
mx = e[i].w;
break;
}
}
}
//cout<<mx<<endl;
int ans = ;
for(int i = ;i <= n;i ++){
if(a[i]*a[i] >= mx)
ans++;
}
cout<<ans<<endl;
}
最新文章
- ARM处理器解析
- [20160731][转]JAVA当中变量什么时候需要初始化
- codeforces 425C
- POJ-2296 Map Labeler 2sat
- js中盒子模型常用的属性你还记得几个?
- Linux用户管理-中
- 如何在.xml中配置Servlet信息
- 《JAVA程序设计》第13周学习总结
- jinja2.exceptions.TemplateNotFound: home/index.html
- Linux下如何阅读开源项目
- 使用 gzexe 快速加密解密文件内容
- httplib和urllib2常用方法
- kvm 客户机加载移动硬盘
- 解决bootstrap多模态框跳转时页面左移问题
- 测试那些事儿—浅谈TCP/IP协议
- 项目中自己一直用到的baseAdapter的类
- WebForms开发方式以及优缺点,来源《ASP.NET MVC企业级实战》
- 20155313 杨瀚 《网络对抗技术》实验八 Web基础
- 安装CDH5时出错 5.68.168.192.in-addr.arpa domain name pointer bogon.
- XPath的初步认识
热门文章
- java 接口实现防盗门功能
- Selenium库
- MySQL 批量修改某一列的值为另外一个字段的值
- PAT L2-013 红色警报
- PHP之常用设计模式
- 【Python3练习题 017】 两个乒乓球队进行比赛,各出三人。甲队为a,b,c三人,乙队为x,y,z三人。已抽签决定比赛名单。有人向队员打听比赛的名单。a说他不和x比,c说他不和x,z比。请编程序找出三队赛手的名单。
- JQuery/JS select标签动态设置选中值、设置禁止选择 button按钮禁止点击 select获取选中值
- [转帖]Linux 硬件和系统配置查看命令小结
- IDEA 各版本在线激活(激活码)
- C# Note10: AutoComplete TextBox in WPF