专栏文章

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 条评论,欢迎与作者交流。

正在加载评论...