kruskal求最小生成树,为何90分?
查看原帖
kruskal求最小生成树,为何90分?
889832
wbc20091030ok楼主2024/9/15 16:51
#include<bits/stdc++.h>
using namespace std;
long long n,m,f[10007];
long long find(long long x){
	return (f[x]==x?x:f[x]=find(f[x]));
}
struct spl{//sit place
	long long x,y;
}s[10007];
struct edge{
	long long u,v;
	long double w;
}e[500007];
bool cmp(edge a,edge b){
	if(a.w<=b.w) return true;
	return false;
}
int main(){
	cin>>n>>m;
	for(long long i=1;i<=n;i++){
		f[i]=i;
	}
	long long a,b;
	for(long long i=1;i<=n;i++){
		cin>>s[i].x>>s[i].y;
	}
	for(long long i=1;i<=m;i++){
		cin>>a>>b;
		a=find(a);
		b=find(b);
		//if(a!=b){
		f[a]=b;
		//}
	}
	long long idx=0;
	for(long long i=1;i<n;i++){
		for(long long j=i+1;j<=n;j++){
			e[++idx].u=i;
			e[idx].v=j;
			e[idx].w=((s[i].x-s[j].x)*(s[i].x-s[j].x)+(s[i].y-s[j].y)*(s[i].y-s[j].y));
			
		}
	}
	sort(e+1,e+idx+1,cmp);
	long long k=0,cnt=m;
	long double ans=0;
	while(1){
		if(cnt>=n-1){
			break;
		}
		k++;
		long long x=find(e[k].u),y=find(e[k].v);
		long double val=e[k].w;
		if(x!=y){
			f[x]=y;
			ans+=sqrt(val);
			cnt++;
		}
	}
	cout<<fixed<<setprecision(2)<<ans<<endl;
	
	return 0;
} 
2024/9/15 16:51
加载中...