ICPC アジア地区予選 2014 F: There is No Alternative

今年ももう終わりですね。

問題概要

原文 → http://judge.u-aizu.ac.jp/onlinejudge/contest/ICPCOOC2014/F.pdf

重み付き無向グラフ $G(V, E)$ が与えられる。 $G$ の最小全域木に必ず含まれる辺はいくつあるか？重みの総和と共に出力せよ。

$3 \leqq V \leqq 500$
$V-1 \leqq E \leqq min(50000, \frac{V(V-1)}{2})$

解説

まず、普通に最小全域木を求めてしまいます。説明のため、ここで使われる辺の集合を $H$ 、最小全域木のコストを $c$ とします。

$H$ に含まれない辺は、最小全域木を構成する時に必要なかった辺ですので、「最小全域木に必ず含まれる辺」になりえないことは明らかです。以下、 $H$ の各要素 $e$ について考えます。

最小全域木に必ず含まれる辺 $e$ というのは、言い換えれば「その辺 $e$ がないと最小全域木が作れない」ということです。したがって、以下を試せばよいです。

$e$ 以外の辺で最小全域木をつくろうとしてみる
最小全域木ができなければ (連結でなければ) 、その辺は「必ず含まれる辺」である
最小全域木はできるが、そのコストが $c$ より大きければ、その辺は「必ず含まれる辺」である

$H$ の要素数は高々 $|V| - 1$ しかありませんので、各辺を無視した最小全域木計算のループは $|V| - 1$ 回です。

クラスカル法を用いれば、辺のソート $O(|E| \log |V|)$ 、各辺を無視した最小全域木計算 $O(|V| |E|)$ より、実行時間内に解くことができます。

ソースコード

プリム法、Union-Find木のソースコードは省略します。

signed main() {
    int n, m; cin >> n >> m;
    Graph(int) G(n);
    vector< Edge<int> > es;
    int s, d, c;
    rep(i,0,m) {
        cin >> s >> d >> c; s--; d--;
        G[s].pb(Edge<int>(s, d, c));
        G[d].pb(Edge<int>(d, s, c));
        es.pb(Edge<int>(d, s, c));
        es.pb(Edge<int>(s, d, c));
    }
    pii ans = pii(0, 0);
    pair< int, vector< Edge<int> > > v = prim(G);
    sort(es.begin(), es.end());
    int E = es.size();
    rep(i,0,v.sc.size()) {
        UnionFind uf(n);
        int res = 0;
        for(int j=0; j<E; j++) {
            Edge<int> e = es[j];
            if(e.to == v.sc[i].from && e.from == v.sc[i].to) continue;
            if(e.to == v.sc[i].to && e.from == v.sc[i].from) continue;
            if(!uf.same(e.from, e.to)) {
                uf.unite(e.from, e.to);
                res += e.cost;
            }
        }

        int par = -1;
        for(int j=0; j<n; j++) {
            if(par == -1) par = uf.find(j);
            else if(par != uf.find(j)) res = INT_MAX;
        }

        if(res > v.fr) {
            ans.fr++;
            ans.sc += v.sc[i].cost;
        }
    }
    printf("%lld %lld\n", ans.fr, ans.sc);
    return 0;
}