40WA求助
查看原帖
40WA求助
794148
cyx20091026楼主2024/12/17 16:59
#include<bits/stdc++.h>
using namespace std;
int m,n;
int dist[10001];
double mx=-100;
int tot,cnt,ans;
struct P{
	int x,y;
}point[10001];
struct E{
	int u,v;
	double w;
}edge[10001];
int fa[10001];
double get(int a,int b){
	return sqrt(pow(point[a].x-point[b].x,2) + pow(point[a].y-point[b].y,2) );
}
bool cmp(E a,E b){
	return a.w<b.w;
}
int find(int x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main(){
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>dist[i];
	}
	cin>>n;
	for(int i=1;i<=n;i++){
		fa[i]=i;
		cin>>point[i].x>>point[i].y;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			tot++;
			edge[tot].u=i;
			edge[tot].v=j;
			edge[tot].w=get(i,j);
		}
	}
	sort(edge+1,edge+1+tot,cmp);
	for(int i=1;i<=tot;i++){
		int eu=find(edge[i].u);
		int ev=find(edge[i].v);
		if(eu==ev) continue;
		fa[eu]=ev;
		mx=edge[i].w;
		cnt++;
		if(cnt==n-1) break;
	}
	for(int i=1;i<=m;i++){
		if(dist[i]>=mx) ans++;
	}
	cout<<ans;
	return 0;
} 
2024/12/17 16:59
加载中...