POJ 3771 - World Islands

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

概要

\(n\) 個の島の座標が与えられる。 島同士を繋ぐ橋を作るにはその距離に比例したコストがかかる。 \(n-1\) 個の島の全域木を作るのに必要な最小のコストを答える。

制約

解法

外す島を選んで \(n\) 回 MST を求めて最小値をとればいい。

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