求助,不知道为什么错了
查看原帖
求助,不知道为什么错了
114015
Marginal_world楼主2020/9/23 22:17
#include<bits/stdc++.h>
using namespace std;
int m,n,ans,k;
int x[100005],y[100005],cnt;
int fa[100000005];
double l,maxn,jump[1000005];
struct node{
	int u,v;
	double w;
}a[100000005];
bool cmp(node x,node y){return x.w<y.w;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
double dis(int nx,int ny,int ex,int ey){
	return sqrt((double)(nx-ex)*(nx-ex)+(double)(ny-ey)*(ny-ey));
}
int main(){
	//freopen("date.in","r",stdin);
	//freopen("sm1.out","w",stdout);
	cin>>m;
	for(int i=1;i<=m;i++)
	cin>>jump[i];
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>x[i]>>y[i];
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			l=dis(x[i],y[i],x[j],y[j]);
			a[++k].u=i;
			a[k].v=j;
			a[k].w=l;
		}
	}
	sort(a+1,a+k+1,cmp);
	for(int i=1;i<=n;i++)
	fa[i]=i;
	for(int i=1;i<=k;i++){
		if(find(a[i].u)!=find(a[i].v)){
			cnt++;
			maxn=a[i].w;
			if(cnt==n-1)break;
		}
	}
	ans=m;
	for(int i=1;i<=m;i++)
	if(jump[i]<maxn)
	ans--;
	cout<<ans;
	return 0;
}

对拍都没找到错————

2020/9/23 22:17
加载中...