#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn_b = 755;
const int maxn_e = maxn_b * (maxn_b - 1) /2;
struct pos{
double x,y;
};
pos A[maxn_b];
int p[maxn_b];
int u[maxn_e];
int v[maxn_e];
int r[maxn_e];
double e[maxn_e];
int find_rep(int u){
return u == p[u]?u:(p[u]=find_rep(p[u]));
}
int cmp(const int i,const int j){
return e[i] < e[j];
}
int main(){
int n,m;
//#define TEST_IN_PC
#ifdef TEST_IN_PC
freopen("uva10397.txt","r",stdin);
#endif
while(scanf("%d",&n) != EOF){
for(int i = 1; i <= n; i++){
scanf("%lf%lf",&A[i].x,&A[i].y);
}
scanf("%d",&m);
for(int i = 1; i <= maxn_e; i++)
r[i] = i;
for(int i = 1; i <= n; i++)
p[i] = i;
for(int i = 1; i <= m; i++){//修改1
int uu,vv;
scanf("%d%d",&uu,&vv);
int x = find_rep(uu);
int y = find_rep(vv);
if(x != y)
p[y] = x;
}
int k = 1;
for(int i = 1; i <=n; i++){//Build Graph
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,e[k++] = d;
}
}
k--;
sort(r + 1, r + 1 + k,cmp);//Kurasal
double ans = 0.0;
for(int i = 1; i <= k; i++){
int ee = r[i];
int uu = find_rep(u[ee]);
int vv = find_rep(v[ee]);
if(uu != vv){
p[uu] = vv;
ans += e[ee];
}
}
printf("%.2lf\n",ans);
}
return 0;
}
//总结注意
//程序要慢慢写,保证每一步程序的语法,下标不出错。
By ACReaper
2013 05 09
分享到:
相关推荐
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的栈实现版本
《算法竞赛入门经典》UVa配套题目pdf版完整
uva10755 ac 代码,可以随意更改下载
这是一支完整的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试题