POJ 1679 - The Unique MST

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

概要

連結な無向グラフが与えられるので，それの最小全域木がユニークであるかどうか答える．

制約

解法

普通に MST を求め，その MST に含まれるいずれかのエッジを使わずに再び MST を作ったとき，最初とコストが等しい MST が作れるかどうかで判定する．

  1 #include <iostream>
  2 #include <vector>
  3 #include <algorithm>
  4 using namespace std;
  5 
  6 class DisjointSet/*{{{*/
  7 {
  8   private:
  9     vector<int> parent;
 10 
 11     int root(int x)
 12     {
 13       if (parent[x] < 0) {
 14         return x;
 15       } else {
 16         parent[x] = root(parent[x]);
 17         return parent[x];
 18       }
 19     }
 20 
 21   public:
 22     explicit DisjointSet(int n) : parent(n, -1) {}
 23 
 24     bool unite(int x, int y)
 25     {
 26       const int a = root(x);
 27       const int b = root(y);
 28       if (a != b) {
 29         if (parent[a] < parent[b]) {
 30           parent[a] += parent[b];
 31           parent[b] = a;
 32         } else {
 33           parent[b] += parent[a];
 34           parent[a] = b;
 35         }
 36         return true;
 37       } else {
 38         return false;
 39       }
 40     }
 41 
 42     bool find(int x, int y) { return root(x) == root(y); }
 43     int size(int x) { return -parent[root(x)]; }
 44 };/*}}}*/
 45 
 46 struct edge {/*{{{*/
 47   int u, v;
 48   typedef int weight_type;
 49   weight_type w;
 50   edge(int s, int d, weight_type w_) : u(s), v(d), w(w_) {}
 51   bool operator<(const edge& that) const { return w < that.w; }
 52 };/*}}}*/
 53 
 54 int solve(const vector<edge>& edges, int N)
 55 {
 56   const int M = edges.size();
 57   int ans = 0;
 58   vector<int> used_edges;
 59   {
 60     DisjointSet s(N);
 61     for (int i = 0; i < M; i++) {
 62       if (s.unite(edges[i].u, edges[i].v)) {
 63         ans += edges[i].w;
 64         used_edges.push_back(i);
 65       }
 66     }
 67   }
 68 
 69   for (vector<int>::const_iterator it(used_edges.begin()); it != used_edges.end(); ++it) {
 70     DisjointSet s(N);
 71     int c = 0;
 72     int n = 1;
 73     for (int i = 0; i < M; i++) {
 74       if (i == *it) {
 75         continue;
 76       }
 77       if (s.unite(edges[i].u, edges[i].v)) {
 78         c += edges[i].w;
 79         ++n;
 80       }
 81     }
 82     if (n == N && c == ans) {
 83       return -1;
 84     }
 85   }
 86   return ans;
 87 }
 88 
 89 int main()
 90 {
 91   int T;
 92   cin >> T;
 93   while (T-- > 0) {
 94     int N, M;
 95     cin >> N >> M;
 96     vector<edge> edges;
 97     for (int i = 0; i < M; i++) {
 98       int u, v, w;
 99       cin >> u >> v >> w;
100       --u;  --v;
101       edges.push_back(edge(u, v, w));
102     }
103     sort(edges.begin(), edges.end());
104 
105     const int ans = solve(edges, N);
106     if (ans == -1) {
107       cout << "Not Unique!" << endl;
108     } else {
109       cout << ans << endl;
110     }
111   }
112   return 0;
113 }
poj/1679.cc