链接: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;
}

最新文章

  1. ARM处理器解析
  2. [20160731][转]JAVA当中变量什么时候需要初始化
  3. codeforces 425C
  4. POJ-2296 Map Labeler 2sat
  5. js中盒子模型常用的属性你还记得几个?
  6. Linux用户管理-中
  7. 如何在.xml中配置Servlet信息
  8. 《JAVA程序设计》第13周学习总结
  9. jinja2.exceptions.TemplateNotFound: home/index.html
  10. Linux下如何阅读开源项目
  11. 使用 gzexe 快速加密解密文件内容
  12. httplib和urllib2常用方法
  13. kvm 客户机加载移动硬盘
  14. 解决bootstrap多模态框跳转时页面左移问题
  15. 测试那些事儿—浅谈TCP/IP协议
  16. 项目中自己一直用到的baseAdapter的类
  17. WebForms开发方式以及优缺点,来源《ASP.NET MVC企业级实战》
  18. 20155313 杨瀚 《网络对抗技术》实验八 Web基础
  19. 安装CDH5时出错 5.68.168.192.in-addr.arpa domain name pointer bogon.
  20. XPath的初步认识

热门文章

  1. java 接口实现防盗门功能
  2. Selenium库
  3. MySQL 批量修改某一列的值为另外一个字段的值
  4. PAT L2-013 红色警报
  5. PHP之常用设计模式
  6. 【Python3练习题 017】 两个乒乓球队进行比赛,各出三人。甲队为a,b,c三人,乙队为x,y,z三人。已抽签决定比赛名单。有人向队员打听比赛的名单。a说他不和x比,c说他不和x,z比。请编程序找出三队赛手的名单。
  7. JQuery/JS select标签动态设置选中值、设置禁止选择 button按钮禁止点击 select获取选中值
  8. [转帖]Linux 硬件和系统配置查看命令小结
  9. IDEA 各版本在线激活(激活码)
  10. C# Note10: AutoComplete TextBox in WPF