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