AOJ 1350 There is No Alternative
問題概要
連結グラフ G が与えられる.一般に G の最小全域木は複数存在しうる.G のすべての最小全域木に必ず含まれている辺を求めよ.
・制約
3 <= N <= 500
N-1 <= M <= min(50000, N(N-1)/2)
解法
最小全域木 T を一つ求める.すると,候補の辺は必ずこの T に含まれている.
よって,T に含まれる辺を一つ使えないようにした状態で,最小全域木 T2 を構築してみる.w(T) != w(T2) ならば,この時使えなくした辺は必ず使う辺である.
計算量は O(MlogM + NMα(N)).
ソースコード
#include <bits/stdc++.h> using namespace std; class union_find { public: union_find(int n) : par_(n, -1) {} void init(int n) { par_.assign(n, -1); } int root(int x) { return par_[x] < 0 ? x : par_[x] = root(par_[x]); } bool unite(int x, int y) { x = root(x); y = root(y); if(x == y) { return false; } else { if(par_[x] < par_[y]) { par_[x] += par_[y]; par_[y] = x; } else { par_[y] += par_[x]; par_[x] = y; } return true; } } bool same(int x, int y) { return root(x) == root(y); } int size(int x) { return -par_[root(x)]; } private: std::vector<int> par_; }; using weight = int; struct edge { int u, v; weight cost; bool operator<(edge const& e) const { return cost < e.cost; } }; using edges = std::vector<edge>; using graph = std::vector<edges>; int main() { int N, M; cin >> N >> M; edges es(M); for(int i=0; i<M; ++i) { cin >> es[i].u >> es[i].v >> es[i].cost; es[i].u--; es[i].v--; } sort(es.begin(), es.end()); int mst_sum = 0; edges mst; union_find uf(N); for(int i=0; i<M; ++i) { if(!uf.same(es[i].u, es[i].v)) { uf.unite(es[i].u, es[i].v); mst.push_back(es[i]); mst_sum += es[i].cost; } } int cnt = 0, res_sum = 0; for(int i=0; i<N-1; ++i) { uf.init(N); int sum = 0; for(auto& e : es) { if(!uf.same(e.u, e.v) && (mst[i].u != e.u || mst[i].v != e.v)) { uf.unite(e.u, e.v); sum += e.cost; } } if(sum != mst_sum) { cnt++; res_sum += mst[i].cost; } } cout << cnt << ' ' << res_sum << endl; }