记录编号	193636	评测结果	AAAAAAAAAA
题目名称	[USACO Dec07] 建造路径	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.535 s
提交时间	2015-10-15 06:23:37	内存使用	16.56 MiB

#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
struct dd{
	int Begin,End;
	double juli;
}jie[1000505];
int jk,n,m,fa[1005],ai,bi,sum;
double data,x[1005],y[1005];
bool vis[1005][1005];
int find(int x){
	if(fa[x]==x) return x;
	fa[x]=find(fa[x]);
	return fa[x];
}
double Dis(int xo,int yo){
	return sqrt((x[xo]-x[yo])*(x[xo]-x[yo])+(y[xo]-y[yo])*(y[xo]-y[yo]));
}
bool comp(const dd & a,const dd & b){
	return a.juli<b.juli;
}
int main(){
    freopen("roads.in","r",stdin);
	freopen("roads.out","w",stdout);
	int yu,lin;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) {
		scanf("%lf%lf",&x[i],&y[i]); fa[i]=i;
	}
	for(int i=1;i<=m;++i) {
		scanf("%d%d",&ai,&bi);
		jie[++jk].Begin=ai; jie[jk].End=bi; jie[jk].juli=0;
		jie[++jk].Begin=bi; jie[jk].End=ai; jie[jk].juli=0;
		vis[ai][bi]=1;
	}
	for(int i=1;i<=n;++i)
	 for(int j=1;j<i;++j){
	   if(i!=j&&!vis[i][j]){
		  double temp=Dis(i,j);
		  jie[++jk].Begin=i; jie[jk].End=j; jie[jk].juli=temp;
		  jie[++jk].Begin=j; jie[jk].End=i; jie[jk].juli=temp;
		  vis[i][j]=1;
	   }
	 }
	 sort(jie+1,jie+jk+1,comp);
	 for(int i=1;i<=jk;++i){
	   yu=find(jie[i].Begin); lin=find(lin=jie[i].End);
	   if(yu!=lin) {
			fa[lin]=yu;
			data+=jie[i].juli;
			sum++;
	   }
	   if(sum==n-1) break;
	 }
	 printf("%.2lf",data);
	 getchar();getchar();
}