AOJ 1350 There is No Alternative

問題

問題リンク：There is No Alternative

N頂点M辺の重み付き無向グラフが与えられる。最小全域木を構成するとき、どのような構成でも必ず使用するような辺の本数とそのコストの総和を求めよ。

• 
• 

解法

最小全域木に1つ辺を追加したとき、その辺によって作られる閉路内にコストの一致する辺があればこれらの辺は交換可能なので必ず使用する辺の条件を満たさない。

よって、最小全域木を作り、閉路をつくるような辺に対してそれぞれ閉路内の辺から追加する辺とコストの一致する辺を候補から除けばよい。

Code

以下はクラスカル法で最小全域木を求めながらDFSで閉路探索を行う実装。計算量は

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> P3;
typedef pair<P ,P> PP;

struct UnionFindTree {
    vector<int> par;
    vector<int> rank;
    vector<int> siz;

    void init(int n) {
        par.resize(n);
        rank.resize(n);
        siz.resize(n);
        for (int i = 0; i < n; i++) {
            par[i] = i;
            rank[i] = 0;
            siz[i] = 1;
        }
    }
    int find(int x) {
        if (par[x] == x) {
            return x;
        } else {
            return par[x] = find(par[x]);
        }
    }
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) rank[x]++;
        par[y] = x;
        siz[x] += siz[y];
    }
    bool is_same(int x, int y) {
        return find(x) == find(y);
    }
    int size(int x) {
        x = find(x);
        return siz[x];
    }
};

int n, m;
vector<P3> es;
UnionFindTree uf;
vector<vector<P> > g;
bool noAlt[50005];

// pre->nowの辺が閉路に含まれるか
bool dfs(int now, int pre, int t, int sc){
    if(now == t) return true;
    for(auto e : g[now]){
        int to = e.first, c = es[e.second].first;
        if(to == pre)continue;
        if(dfs(to, now, t, sc)){
            if(c == sc) noAlt[e.second] = false;  // 同じコストは除く
            return true;
        }
    }
    return false;
}

int main() {
    cin >> n >> m;
    for(int i=0;i<m;i++){
        int s, d, c;
        cin >> s >> d >> c;
        s--; d--;
        es.push_back({c,{s,d}});
    }
    // Kruskal法
    sort(es.begin(), es.end());
    uf.init(n);
    g.resize(n);
    for(int i=0;i<m;i++){
        auto e = es[i];
        int c = e.first, u = e.second.first, v = e.second.second;
        if(!uf.is_same(u,v)){  // 候補に加える
            uf.unite(u,v);
            noAlt[i] = true;
            g[u].push_back({v, i});  // 行先と辺番号のペア
            g[v].push_back({u, i});
        }
        else{
            // 閉路内でコストがcと同じ辺を候補から除く
            dfs(u, -1, v, c);
        }
    }
    int ecnt = 0, csum = 0;
    for(int i=0;i<m;i++){
        if(noAlt[i]){
            ecnt++;
            csum += es[i].first;
        }
    }
    cout << ecnt << " " << csum << endl;
    return 0;
}