POJ 3625 - Building Roads

http://poj.org/problem?id=3625

概要

\(N\) 個のファームがそれぞれ座標 \((X_i, Y_i)\) にある。 すでに \(M\) 本の道がファームを双方向に繋いでいる。

すべてのファームを繋ぐのに追加する必要がある最小の道の長さを答える。

制約

• \(1 \le N \le 1000\)
• \(0 \le X_i, Y_i \le 10 ^ 6\)
• \(1 \le M \le 1000\)

解法

最小全域木を求めるだけ。

 1 #include <cstdio>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <complex>
 5 using namespace std;
 6 typedef complex<double> P;
 7 
 8 struct DisjointSet/*{{{*/
 9 {
10   vector<int> parent;
11 
12   int root(int x)
13   {
14     if (parent[x] < 0) {
15       return x;
16     } else {
17       parent[x] = root(parent[x]);
18       return parent[x];
19     }
20   }
21 
22   explicit DisjointSet(int n) : parent(n, -1) {}
23 
24   bool unite(int x, int y)
25   {
26     const int a = root(x);
27     const int b = root(y);
28     if (a != b) {
29       if (parent[a] < parent[b]) {
30         parent[a] += parent[b];
31         parent[b] = a;
32       } else {
33         parent[b] += parent[a];
34         parent[a] = b;
35       }
36       return true;
37     } else {
38       return false;
39     }
40   }
41 
42   bool find(int x, int y) { return root(x) == root(y); }
43   int size(int x) { return -parent[root(x)]; }
44 };/*}}}*/
45 
46 struct edge
47 {
48   int u, v;
49   double w;
50   edge(int a, int b, double c) : u(a), v(b), w(c) {}
51   bool operator<(const edge& e) const { return w < e.w; }
52 };
53 
54 double kruskal(DisjointSet& s, const vector<edge>& es)
55 {
56   const int N = s.parent.size();
57   double ans = 0;
58   for (vector<edge>::const_iterator it = es.begin(); s.size(0) < N && it != es.end(); ++it) {
59     if (s.unite(it->u, it->v)) {
60       ans += it->w;
61     }
62   }
63   return ans;
64 }
65 
66 int main()
67 {
68   int N, M;
69   scanf("%d %d", &N, &M);
70   vector<P> ps;
71   for (int i = 0; i < N; i++) {
72     int x, y;
73     scanf("%d %d", &x, &y);
74     ps.push_back(P(x, y));
75   }
76   DisjointSet s(N);
77   for (int i = 0; i < M; i++) {
78     int u, v;
79     scanf("%d %d", &u, &v);
80     --u;  --v;
81     s.unite(u, v);
82   }
83 
84   vector<edge> es;
85   for (int i = 0; i < N; i++) {
86     for (int j = i+1; j < N; j++) {
87       if (!s.find(i, j)) {
88         es.push_back(edge(i, j, abs(ps[i] - ps[j])));
89       }
90     }
91   }
92   sort(es.begin(), es.end());
93   printf("%.2f\n", kruskal(s, es));
94   return 0;
95 }