专栏文章
debug2
个人记录参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mipckmxb
- 此快照首次捕获于
- 2025/12/03 09:47 3 个月前
- 此快照最后确认于
- 2025/12/03 09:47 3 个月前
CPP
#include<bits/stdc++.h>
using namespace std;
struct Edge{
int u,v,w;
}e[500001];
int maxd=-1,m,n,x,y,l,ans;
int fa[1001],d[1001];
int tx[1001],ty[1001];
int findfa(int now){
if(fa[now]==now){
return now;
}
return fa[now]=findfa(fa[now]);
}
bool cmp(Edge &a,Edge &b){
return a.w<b.w;
}
void Kruskal(int s){
sort(e+1,e+s+1,cmp);
int note=0;
for(int i=1;i<=s;i++){
int x=findfa(e[i].u),y=findfa(e[i].v);
if(x!=y){
fa[x]=y;
maxd=max(maxd,e[i].w);
++note;
if(note==n-1){
break;
}
}
}
}
int main(){
cin>>m;
for(int i=1;i<=m;++i){
cin>>d[i];
}
cin>>n;
for(int i=1;i<=n;++i){
cin>>x>>y;
tx[i]=x,ty[i]=y;
}
for(int i=1;i<=n;++i){
for(int j=i+1;j<=n;++j){
++l;
e[l].u=i,e[l].v=j,e[l].w=pow(tx[i]-tx[j],2)+pow(ty[i]-ty[j],2);
}
}
Kruskal(l);
for(int i=1;i<=m;++i){
if(pow(d[i],2)>=maxd){
++ans;
}
}
cout<<ans;
return 0;
}
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...