比赛 20181007 评测结果 AEAEEEEEEE
题目名称 建造路径 最终得分 20
用户昵称 tx_siny 运行时间 0.435 s
代码语言 C++ 内存使用 3.19 MiB
提交时间 2018-10-07 10:44:06
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
typedef long double ld;
inline int read(){
	int f=1,x=0;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x*f;
}
#define read(x) x=read()
struct Point{
	int x,y;
};
Point p[maxn];
struct Line{
	int x,y;
	ld dis;
	bool friend operator <(Line x,Line y){
		return x.dis<y.dis;
	}
};
int l_num;
Line l[maxn];
int m,n,f[maxn];
ld ans;
inline ld getdis(Point a,Point b){
	int x=b.x-a.x;
	int y=b.y-a.y;
	return sqrt(x*x+y*y);
}
int father(int k){
	return f[k]==k?f[k]:f[k]=father(f[k]);
}
void Init(){
	read(n);read(m);
	for(int i=1;i<=n;i++){
		read(p[i].x);
		read(p[i].y);
	}
	for(int i=1;i<=n;i++)
	  for(int j=i+1;j<=n;j++){
	  	Line now;
	  	now.x=i;now.y=j;
	  	now.dis=getdis(p[i],p[j]);
	  	l[++l_num]=now;
	  }
	for(int i=1;i<=n;i++)
	  f[i]=i;
	sort(l+1,l+l_num+1);
	for(int i=1;i<=m;i++){
		int x,y;
		read(x);read(y);
		int fx=father(x);
		int fy=father(y);
		if(fx==fy) continue;
		f[fx]=fy;
	}
}
void kruskal(){
	ans=0;
	for(int i=1;i<=l_num;i++){
		int fx=father(l[i].x);
		int fy=father(l[i].y);
		if(fx==fy) continue;
		ans+=l[i].dis;
		f[fx]=fy;
	}
}
int main(){
	freopen("roads.in","r",stdin);
	freopen("roads.out","w",stdout);
	Init();
	kruskal();
	cout<<fixed<<setprecision(2)<<ans;
	return 0;
}