hogecoder

tsutaj 競技プログラミングの記録

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

ただのライブラリ貼るだけ問題じゃないので、好きな問題です。この手の問題たくさん解けるようになりたいですね。

おそらくこれが今年最後の投稿になるでしょう。良いお年を。