记录编号	220381	评测结果	AAAAAAAAAA
题目名称	[USACO Dec07] 建造路径	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.489 s
提交时间	2016-01-18 14:54:17	内存使用	15.56 MiB

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int ufs[1005];
int x[1005],y[1005];
int find(int a){
	if(ufs[a]!=a)ufs[a] = find(ufs[a]);
	return ufs[a];
}
void link(int a,int b){
	ufs[find(a)] = find(b);
}
struct e{
	int v1,v2;
	double w;
}d[1000000];
int t;
bool cmp(e a,e b){
	return a.w<b.w;
}
int main(){
	freopen("roads.in","r",stdin);
	freopen("roads.out","w",stdout);
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i = 1;i<=n;++i){
		scanf("%d %d",x+i,y+i);
		ufs[i] = i;
	}
	long long p,q;
	int num = 1;
	for(int i = 0;i<m;++i){
		scanf("%lld %lld",&p,&q);
		if(find(p)!=find(q)){
			link(p,q);
			if(++num==n){
				printf("0.00");
				break;
			}
		}
	}
	for(int i = 1;i<=n;++i)
	    for(int j = i+1;j<=n;++j){
			if(find(i)!=find(j)){
				d[t].v1 = i;
				d[t].v2 = j;
				p = x[i]-x[j];q = y[i]-y[j];
				d[t++].w = sqrt(p*p+q*q);
			}
	    }
	sort(d,d+t,cmp);
	double ans = 0;
	for(int i = 0;i<t;++i){
		if(find(d[i].v1)!=find(d[i].v2)){
			link(d[i].v1,d[i].v2);
			ans+=d[i].w;
			if(++num==n){
				printf("%.2lf",ans);
				break;
			}
		}
 	}

	fclose(stdin);fclose(stdout);
	return 0;
}