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;
}