POJ 2560 - Freckles

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

概要

二次元座標上に n 個の点が与えられ，それらを直線で結んでいく． 直線で結ぶ際に，長さに比例したインクが消費される．

すべての点を繋ぐのに必要なインクの量を最小化したときの長さの和を答える．

制約

• 0 < n <= 100

解法

点と点の距離をコストとみて最小全域木を作る．

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