POJ 1639 - Picnic Planning

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

概要

M 本の道が公園と N 人の家を繋いでいる．

K 台までの車を使って N 人全員が公園に行けるようにしたい． そのときの車の走行距離の合計の最小値を答える．

ただし，1台の車に何人でも乗ることができるとする．

制約

解法

公園からの枝を K 本まで使って最小全域木を作ればいい． M が小さいので，K 本の枝の選び方は全通り試しても問題無い．

  1 #include <iostream>
  2 #include <vector>
  3 #include <map>
  4 #include <algorithm>
  5 using namespace std;
  6 
  7 class DisjointSet/*{{{*/
  8 {
  9   private:
 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   public:
 23     explicit DisjointSet(int n) : parent(n, -1) {}
 24 
 25     bool unite(int x, int y)
 26     {
 27       const int a = root(x);
 28       const int b = root(y);
 29       if (a != b) {
 30         if (parent[a] < parent[b]) {
 31           parent[a] += parent[b];
 32           parent[b] = a;
 33         } else {
 34           parent[b] += parent[a];
 35           parent[a] = b;
 36         }
 37         return true;
 38       } else {
 39         return false;
 40       }
 41     }
 42 
 43     bool find(int x, int y) { return root(x) == root(y); }
 44     int size(int x) { return -parent[root(x)]; }
 45 };/*}}}*/
 46 
 47 struct edge {
 48   int u, v;
 49   int w;
 50   edge(int s, int d, int w_) : u(s), v(d), w(w_) {}
 51   bool operator<(const edge& that) const { return w < that.w; }
 52 };
 53 
 54 int kruskal(const vector<edge>& edges, const int N, const vector<int>& avail)
 55 {
 56   DisjointSet s(N);
 57   int ttl = 0;
 58   const int M = edges.size();
 59   for (int i = 0; i < M && s.size(0) < N; i++) {
 60     if (avail[i] && s.unite(edges[i].u, edges[i].v)) {
 61       ttl += edges[i].w;
 62     }
 63   }
 64   if (s.size(0) == N) {
 65     return ttl;
 66   } else {
 67     return 10000000;
 68   }
 69 }
 70 
 71 int numbering(map<string,int>& m, const string& name)
 72 {
 73   const map<string,int>::const_iterator it = m.find(name);
 74   if (it == m.end()) {
 75     const int n = m.size();
 76     m.insert(make_pair(name, n));
 77     return n;
 78   } else {
 79     return it->second;
 80   }
 81 }
 82 
 83 int main()
 84 {
 85   int M;
 86   cin >> M;
 87   map<string, int> m;
 88   vector<edge> edges;
 89   for (int i = 0; i < M; i++) {
 90     string s1, s2;
 91     int w;
 92     cin >> s1 >> s2 >> w;
 93     const int u = numbering(m, s1);
 94     const int v = numbering(m, s2);
 95     edges.push_back(edge(u, v, w));
 96   }
 97   sort(edges.begin(), edges.end());
 98   const int N = m.size();
 99   int K;
100   cin >> K;
101 
102   const int root = m["Park"];
103   vector<int> v;
104   for (int i = 0; i < M; i++) {
105     if (edges[i].u == root || edges[i].v == root) {
106       v.push_back(i);
107     }
108   }
109   const int size = v.size();
110 
111   vector<int> avail(M, 1);
112   vector<int> a(size, 0);
113   for (int i = 0; i < min(size, K); i++) {
114     a[i] = 1;
115   }
116   sort(a.begin(), a.end());
117   int ans = 10000000;
118   do {
119     for (int i = 0; i < size; i++) {
120       avail[v[i]] = a[i];
121     }
122     ans = min(ans, kruskal(edges, N, avail));
123   } while (next_permutation(a.begin(), a.end()));
124 
125   cout << "Total miles driven: " << ans << endl;
126   return 0;
127 }
poj/1639.cc