#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 15024;
int u[maxn];
int v[maxn];
double w[5 * maxn];
int r[5 * maxn];
int fa[maxn];
struct pos{
double x,y;
};
pos A[maxn];
int cmp(const int a,const int b){
return w[a] < w[b];
}
int find(int root){
return root == fa[root]?root:find(fa[root]);
}
int main(){
int tc;
scanf("%d",&tc);
for(int t = 1; t <= tc; t++){
int n;
scanf("%d",&n);
for(int i = 1 ; i <= n; i++){
scanf("%lf%lf",&A[i].x,&A[i].y);
}
memset(w,0,sizeof(w));
int k = 1;
for(int i = 1; i <= n; i++){//构建完全图
for(int j = i + 1;j <= n; j++){
double d = sqrt((A[i].x - A[j].x) * (A[i].x - A[j].x) + (A[i].y - A[j].y) * (A[i].y - A[j].y));
u[k] = i,v[k] = j,w[k++] = d;
}
}
double ans = 0.0;
int num_e = n * (n - 1) /2;
for(int i = 1; i <= n; i++)
fa[i] = i;
for(int i = 1; i <= num_e; i++)
r[i] = i;
sort(r + 1,r + 1 + num_e,cmp);//
for(int i = 1; i <= num_e;i++){
int e = r[i];
int x = find(u[e]);//找到起点
int y = find(v[e]);
if( x != y){
fa[x] = y;
ans += w[e];
}
}
printf("%s", t == 1? "" : "\n");
printf("%.2lf\n",ans);
}
return 0;
}
2013 05 07
By ACReaper
分享到:
相关推荐
uva272
UVA109的题解,经测试完全正确,还附有题解。
有uva刘汝佳文件夹的50道题解,从数据结构开始,以后慢慢上传
包含UVA在线OJ系统的绝大部分的示例代码,并都已AC,可在刷题时参考
UVa在我看来是比较全的一个题解,希望能帮助大家。欢迎下载。
uva最全ac代码
uva531最长公共子序列问题水题,应用简单的dp即可ac有更快速的方法欢迎讨论
1.Uva_base的编译 在编译球队时,则需要在当前球队文件夹下打开终端输入执行以下命令(以下命令都是在root下执行的): ./configure make clean make 如果运行Uva_base后,出现球员越界或掉线的情况,就重新...
UVA 题目,不是很难,试试吧
uva357的栈实现版本
uva10755 ac 代码,可以随意更改下载
《算法竞赛入门经典》UVa配套题目pdf版完整
这是一支完整的uva球队,包含所有基本模块,初者可在上修改得到自己的球队
世界著名大学UVA OJ平台上的题目部分分类,分的不好请原谅。
uva_trilearn2002 源代码
开源项目-codingsince1985-UVa.zip,Been solving UVa Online Judge Problems in Golang for one year (and counting)
这里面全部为在Uva Online Judge上面的部分题目的解答,里面提供了解答使用的源代码。
主要是uvaoj习题相关题目 练习题目
UVA 499 Solution in C/ C++
PDF试题