比赛 20181007 评测结果 AAAAAAAAAA
题目名称 建造路径 最终得分 100
用户昵称 梦那边的美好ET 运行时间 0.569 s
代码语言 C++ 内存使用 18.43 MiB
提交时间 2018-10-06 18:38:29
显示代码纯文本
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;
struct hs{double l;int x,y;}d[1000010];
int a[1010],b[1010],fa[1010],n,m,a1,a2,sum=0;
double ans=0.0;
int find(int p){return fa[p]=(fa[p]==p)?p:find(fa[p]);}
bool bk(hs p1,hs p2){return p1.l<p2.l;}
int main(){
	freopen("roads.in","r",stdin);
	freopen("roads.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
	if(m)for(int i=1;i<=m;i++){
	    scanf("%d%d",&a1,&a2);
		int f1=find(a1),f2=find(a2);
		if(f1==f2)continue;
		fa[f2]=f1;
	}
	for(int i=1;i<n;i++){
		for(int j=i+1;j<=n;j++){
		    int f1=find(i),f2=find(j);
		    if(f1==f2)continue;	
            d[++sum].x=i;d[sum].y=j;
            d[sum].l=(double)sqrt((double)(a[i]-a[j])*(a[i]-a[j])+(double)(b[i]-b[j])*(b[i]-b[j]));
		}
	}
	sort(d+1,d+1+sum,bk);
	for(int i=1;i<=sum;i++){
		int f1=find(d[i].x),f2=find(d[i].y);
		if(f1==f2)continue;
		fa[f2]=f1;ans+=d[i].l;
	}
	printf("%.2f",ans);
	return 0;
}