| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Maybe it can help you#include <iostream>
#include <cstdio>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
#define int long long
using namespace std;
int n, m, par[1000 + 10], rank[1000 + 10];
vector<pair<double, pair<int, int> > >e;
pair<int, int>p[1000 + 10];
void init(){
for(int i = 1; i <= n; i++){
par[i] = i;
for(int j = i + 1; j <= n; j++){
e.push_back(make_pair(sqrt((p[j].first - p[i].first) * (p[j].first - p[i].first) + (p[j].second -
p[i].second) * (p[j].second - p[i].second)), make_pair(i, j)));
}
}
sort(e.begin(), e.end());
}
int findpar(int x){
if(par[x] == x){
return x;
}
return par[x] = findpar(par[x]);
}
void join(int x, int y){
int fx = findpar(x), fy = findpar(y);
if(fx == fy){
return;
}
if(rank[fx] > rank[fy]){
par[fy] = fx;
}
else if(rank[fy] > rank[fx]){
par[fx] = fy;
}
else if(rank[fy] == rank[fy]){
par[fx] = fy;
rank[fy]++;
}
}
double kruskal(){
double ret = 0;
for(int i = 0; i < e.size(); i++){
if(findpar(e[i].second.first) != findpar(e[i].second.second)){
ret += e[i].first;
join(e[i].second.first, e[i].second.second);
}
}
return ret;
}
main(){
scanf("%lld %lld", &n, &m);
for(int i = 1; i <= n; i++){
scanf("%lld %lld", &p[i].first, &p[i].second);
}
init();
for(int i = 0; i < m; i++){
int x, y;
scanf("%lld %lld", &x, &y);
join(x, y);
}
printf("%.2f\n", kruskal());
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator