HDU - 1875 最小生成树

#include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <cmath> #include <cstring> using namespace std; int fa[1000]; typedef pair<int, int> p; struct edge { int come, to; double d; bool operator <(const edge &p1) { return d < p1.d; } }d[3000]; p pp[5000]; vector<edge> q; int getf(int x) { if(x == fa[x]) return x; return fa[x] = getf(fa[x]); } void init() { for(int i = 0; i < 1000; i++) fa[i] = i; q.clear(); memset(pp, 0, sizeof(pp)); } void Union(int x, int y) { x = getf(x); y = getf(y); if(x == y) return; fa[x] = y; } double dis(p p1, p p2) { return sqrt((p1.first - p2.first) * (p1.first - p2.first) + (p1.second - p2.second) * (p1.second - p2.second)); } bool OK(int n) { int father = getf(1); for(int i = 2; i <= n; i++) if(father != getf(i)) return 0; return 1; } int main() { int T; cin >> T; while(T--) { int n; cin >> n; init(); for(int i = 1; i <= n; i++) cin >> pp[i].first >> pp[i].second; for(int i = 1; i < n; i++) { for(int j = i + 1; j <= n; j++) { double d = dis(pp[i], pp[j]); if(d >= 10 && d <= 1000.0) { edge s; s.come = i; s.to = j; s.d = d; q.push_back(s); } } } sort(q.begin(), q.end()); double sum = 0; for(int i = 0; i < q.size(); i++) { if(getf(q[i].come) != getf( q[i].to)) { sum += q[i].d; Union(q[i].come, q[i].to); } } if(OK(n)) printf("%.1lf\n", sum * 100); else printf("oh!\n"); } return 0; }