不懂就问---Kruskal 10分 WA
查看原帖
不懂就问---Kruskal 10分 WA
1010139
Sirus_Black楼主2023/7/24 09:55
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m,e;
struct node1{
	int x,y;
}d[1005];
struct node{
	int x,y;
	double w;
}a[1000005];
int dis[1005];
int p[1000005];
bool cmp(node x,node y){
	return x.w<y.w;
}
int fd(int x){
	if(p[x]!=x){
		p[x]=fd(p[x]);
	}
	return p[x];
}
int kruscal(){
	int sum=0;
	double maxn=0;
	sort(a+1,a+e+1,cmp);
	for(int i=1;i<=e;i++){
		int u=fd(a[i].x),v=fd(a[i].y);
		if(u!=v){
			p[u]=v;
			sum++;
			maxn=a[i].w;
			if(sum==n-1){
				break;
			}
		}
	}
	return maxn;
}
int main(){
	cin>>m;
	for(int i=1;i<=m;i++){
		cin>>dis[i];
	}
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>d[i].x>>d[i].y;
	}
	for(int i=1;i<=n;i++){
		p[i]=i;
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
				a[++e].x=i;
				a[e].y=j;
		a[e].w=sqrt(abs(a[i].x.a[j].x)*abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)*abs(a[i].y-a[j].y));
		}
	}	
	int ans=kruscal();
	int sum=0;
	for(int i=1;i<=m;i++){
		if(dis[i]>=ans){
			sum++;
		}
	}
	cout<<sum;
	return 0;
}
2023/7/24 09:55
加载中...