萌新Kruskal代码90分最后一个点MLE求助
查看原帖
萌新Kruskal代码90分最后一个点MLE求助
147879
鲷个几爸楼主2020/8/8 21:45
#include <bits/stdc++.h>
using namespace std;
struct as{
	int a,b;
	double len;
}f[500005];
int n,m,fa[500006],op=0;
//double zb[1005][3];
int gf(int x){
	if(fa[x]!=x)fa[x]=gf(fa[x]);
	return fa[x];
}
bool sd(as v,as n){
	return v.len<n.len;
}double ans=0;
int cnt=0,k=0,l=0;
double zui[1005];
int Kruskal(){
	for(int k=1;k<=op;k++){
		int x=gf(f[k].a),y=gf(f[k].b);
		if(x!=y){
			fa[x]=y;
			ans+=f[k].len;cnt++;
//			zui[cnt]=f[k].len;
		}
		if(cnt==n-1)break;
	}
	printf("%.2lf",ans);
	return 0;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	scanf("%lf%lf",&zb[i][1],&zb[i][2]);
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i<j){
		op++;f[op].a=i;f[op].b=j;
		f[op].len=(double)sqrt((zb[i][1]-zb[j][1])*(zb[i][1]-zb[j][1])+(zb[i][2]-zb[j][2])*(zb[i][2]-zb[j][2])); 
	}
	for(int i=1;i<=m;i++){
		int h,j;
		scanf("%d%d",&h,&j);
		op++;	
		f[op].a=h,f[op].b=j;
		f[op].len=0;
	}
	for(int i=1;i<=n;i++)fa[i]=i;
	sort(f+1,f+1+op,sd);
	Kruskal();
    return 0;
}
2020/8/8 21:45
加载中...