POJ 2075 - Tangled in Cables

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

概要

N 個の家を M 本の道が繋いでおり，i 番目の道の長さは D[i] である．

N 個すべての家を道に沿って繋ぐときに必要な最短のケーブルの長さを答える．

ただし，持っているケーブルの長さは L しかないので，L の長さですべての家を繋げられないときは「Not enough cable」と答える．

制約

？？？

解法

最小全域木を求めるだけ．

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <vector>
  4 #include <queue>
  5 #include <map>
  6 using namespace std;
  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)
 45     {
 46       return root(x) == root(y);
 47     }
 48 
 49     int size(int x)
 50     {
 51       return -parent[root(x)];
 52     }
 53 };/*}}}*/
 54 
 55 struct edge {/*{{{*/
 56   int u, v;
 57   typedef double weight_type;
 58   weight_type w;
 59   edge(int s, int d, weight_type w_) : u(s), v(d), w(w_) {}
 60   bool operator<(const edge& rhs) const
 61   {
 62     return w > rhs.w;
 63   }
 64 };/*}}}*/
 65 
 66 template <class Edge>
 67 typename Edge::weight_type kruskal(priority_queue<Edge> edges, const int N)/*{{{*/
 68 {
 69   DisjointSet s(N);
 70   typename Edge::weight_type ttl = 0;
 71   while (s.size(0) < N && !edges.empty()) {
 72     const Edge e = edges.top();
 73     edges.pop();
 74     if (s.unite(e.u, e.v)) {
 75       ttl += e.w;
 76     }
 77   }
 78   return ttl;
 79 }/*}}}*/
 80 
 81 int main()
 82 {
 83   double L;
 84   cin >> L;
 85   int N;
 86   cin >> N;
 87   map<string,int> m;
 88   for (int i = 0; i < N; i++) {
 89     string name;
 90     cin >> name;
 91     m.insert(make_pair(name, i));
 92   }
 93   int M;
 94   cin >> M;
 95   priority_queue<edge> edges;
 96   for (int i = 0; i < M; i++) {
 97     string src, dst;
 98     double c;
 99     cin >> src >> dst >> c;
100     const int s = m[src];
101     const int d = m[dst];
102     edges.push(edge(s, d, c));
103   }
104 
105   const double r = kruskal(edges, N);
106   if (r <= L) {
107     printf("Need %.1f miles of cable\n", r);
108   } else {
109     puts("Not enough cable");
110   }
111   return 0;
112 }