为什么会Re???求助大佬!!!救救萌新吧
查看原帖
为什么会Re???求助大佬!!!救救萌新吧
526794
青莲之歌楼主2022/1/29 11:57
#include<bits/stdc++.h>
using namespace std;
int n,m,sum,num,f[1005],x[1005],y[1005];
double ans;
struct node{
	int u,v;
	double w;
}edge[1005];
bool cmp(node a,node b){
	if(a.w==b.w)return a.u<b.u;
	return a.w<b.w;
}
int find(int a){
	if(a==f[a])return a;
	else return f[a]=find(f[a]);
}
double dis(int a,int b){
	return (double)(sqrt((double)(x[a]-x[b])*(x[a]-x[b])+(double)(y[a]-y[b])*(y[a]-y[b])));
}
void add(int a,int b,double c){
    num++;
    edge[num].u=a;
	edge[num].v=b;
	edge[num].w=c;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		f[i]=i;
		scanf("%d%d",&x[i],&y[i]);
	}
	for(int i=1;i<=n;i++)
	    for(int j=i+1;j<=n;j++){
	    	add(i,j,dis(i,j));
		}
	for(int i=1;i<=m;i++){
		int su,sv;
		scanf("%d%d",&su,&sv);
		add(su,sv,0.0);
	}
	sort(edge+1,edge+num+1,cmp);
    for(int i=1;i<=num;i++){
		int fu=find(edge[i].u),fv=find(edge[i].v);
		if(fu!=fv){
			f[fu]=fv;
			ans+=edge[i].w;
			sum++;
		}
		if(sum==n-1){
			printf("%.2lf",ans);
			exit(0);
		}
	}
	return 0;
}
2022/1/29 11:57
加载中...