POJ 1251 - Jungle Roads

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

概要

n 個の村があり，m 個の橋が村と村を繋いでいる． それぞれの橋には維持費がある．

どの村からどの村へも行ける状態を保ちつつ，いくつか橋を取り壊して維持費の和を最小にしたい． そのときの和を答える．

制約

• 1 < n < 27
• m <= 75

解法

最小全域木の練習みたいな問題． 当時はプリム法で解いてた．サイズが小さいからどう実装しても大丈夫そう．

 1 #include <iostream>
 2 #include <vector>
 3 #include <set>
 4 #include <limits>
 5 using namespace std;
 6 
 7 int prim(vector<vector<int> >& g)
 8 {
 9   const int N = g.size();
10   set<int> visited;
11   visited.insert(0);
12   
13   int ans = 0;
14 
15   while (visited.size() < N) {
16     int next_node = -1;
17     int weight = -1;
18     int min_cost = numeric_limits<int>::max();
19 
20     for (set<int>::const_iterator it(visited.begin()); it != visited.end(); ++it) {
21       for (int i = 0; i < N; i++) {
22         if (visited.find(i) == visited.end() && g[*it][i] < min_cost) {
23           min_cost = g[*it][i];
24           weight = g[*it][i];
25           next_node = i;
26         }
27       }
28     }
29     visited.insert(next_node);
30     ans += weight;
31   }
32   return ans;
33 }
34 
35 int main(void)
36 {
37   int N;
38   while (cin >> N && N > 0) {
39     vector<vector<int> > g(N, vector<int>(N, numeric_limits<int>::max()));
40 
41     for (int i = 0; i < N-1; i++) {
42       char c;
43       int k;
44       cin >> c >> k;
45       for (int j = 0; j < k; j++) {
46         char d;
47         int w;
48         cin >> d >> w;
49         g[c-'A'][d-'A'] = g[d-'A'][c-'A'] = w;
50       }
51     }
52     cout << prim(g) << endl;
53   }
54   return 0;
55 }