POJ 1258 - Agri-Net

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

概要

N 個の農場を光ファイバーで繋ぐ． ある農場と別の農場を繋ぐのに必要なコストが与えられる．

どの農場から別のどの農場への経路が存在するように繋いだとき，それに必要な最小のコストを答える．

制約

解法

最小全域木．なぜか priority_queue を使ってた．

 1 #include <iostream>
 2 #include <vector>
 3 #include <queue>
 4 using namespace std;
 5 
 6 class DisjointSet {
 7   private:
 8     vector<int> parent;
 9 
10     int root(int x)
11     {
12       if (parent[x] < 0) {
13         return x;
14       } else {
15         parent[x] = root(parent[x]);
16         return parent[x];
17       }
18     }
19 
20   public:
21     DisjointSet(int size) : parent(size, -1) {}
22 
23     bool unite(int x, int y)
24     {
25       const int a = root(x);
26       const int b = root(y);
27       if (a != b) {
28         if (parent[a] < parent[b]) {
29           parent[a] += parent[b];
30           parent[b] = a;
31         } else {
32           parent[b] += parent[a];
33           parent[a] = b;
34         }
35         return true;
36       } else {
37         return false;
38       }
39     }
40 
41     bool find(int x, int y)
42     {
43       return root(x) == root(y);
44     }
45 
46     int size(int x)
47     {
48       return -parent[root(x)];
49     }
50 };
51 
52 struct Edge {
53   int from, to, weight;
54   Edge(int f, int t, int w) : from(f), to(t), weight(w) {}
55   
56   bool operator<(const Edge& e) const
57   {
58     return weight > e.weight;
59   }
60 };
61 
62 int kruskal(priority_queue<Edge> edges, const int N)
63 {
64   DisjointSet s(N);
65   int ttl = 0;
66   while (s.size(0) < N) {
67     const Edge e = edges.top();
68     edges.pop();
69     if (s.unite(e.from, e.to)) {
70       ttl += e.weight;
71     }
72   }
73   return ttl;
74 }
75 
76 int main(void)
77 {
78   int N;
79   while (cin >> N) {
80     priority_queue<Edge> edges;
81     for (int i = 0; i < N; i++) {
82       for (int j = 0; j < N; j++) {
83         int w;
84         cin >> w;
85         edges.push(Edge(i, j, w));
86       }
87     }
88     cout << kruskal(edges, N) << endl;
89   }
90 }
poj/1258.cc