P2504 只有10分 求大佬找错
  • 板块题目总版
  • 楼主mtz_FWB
  • 当前回复3
  • 已保存回复3
  • 发布时间2020/10/21 22:27
  • 上次更新2023/11/5 10:12:27
查看原帖
P2504 只有10分 求大佬找错
84704
mtz_FWB楼主2020/10/21 22:27
#include<bits/stdc++.h>
using namespace std;
int m,n,fa[2020000],b[2020000][3];
double a[2020000];
struct node{
	int u,v;
	double w;
}edge[2020000];
int find(int x){
	if(x!=fa[x])fa[x]=find(fa[x]);
	return fa[x];
}
bool cmp(node a,node b){
	return a.w<b.w;
}
int main(){
	cin>>m;
	int i,j,cnt=0,sum=0,ans=0;
	double maxn=-1;
	for(i=1;i<=m;i++)cin>>a[i];
	cin>>n;
	for(i=1;i<=n;i++)
	  for(j=1;j<=2;j++)cin>>b[i][j];
	for(i=1;i<=n;i++)
	  for(j=1;j<=n;j++)if(i!=j){
			sum++;
			edge[sum].u=i;
			edge[sum].v=j;
			edge[sum].w=sqrt((b[i][1]-b[j][1])*(b[i][1]-b[j][1])+(b[i][2]-b[j][2]*(b[i][2]-b[j][2])));
	  }
	for(i=1;i<=n;i++)fa[i]=i;
	sort(edge+1,edge+1+sum,cmp);
	for(i=1;i<=sum;i++){
		int root_x=find(edge[i].u);
		int root_y=find(edge[i].v);
		if(root_x!=root_y){
			fa[root_x]=root_y;
			maxn=max(maxn,edge[i].w);
			if(++cnt==sum-1)break;
		}
	}
	for(i=1;i<=m;i++)if(a[i]>=maxn)ans++;
	cout<<ans;
	return 0;
}
2020/10/21 22:27
加载中...