CODE FESTIVAL 2016 Elimination Tournament Round 1: A - グラフ / Graph

問題記録 AtCoder CODE FESTIVAL

問題概要

辺に正整数の重みが設定されたN頂点M辺の無向グラフと、Q個のクエリが与えられる。i個目のクエリでは頂点SiとTiが指定される。各クエリにおいて、「SiまたはTiを始点としたとき、集合に含まれる辺のみを使ってすべての頂点にたどりつくことができる」という条件を満たすように辺集合を選ぶとき、集合に含まれる辺の重みの和の最小値を求めよ。

N <= 4000

M <= 400000

Q <= 100000

解法

クエリ1回であれば最小全域森っぽいものを求めればいけそうだが、それを毎回計算するのは不可能である。ここで重要な発想はSiとTiを同一視して縮約しまうことである。このようにすると「SiまたはTi」という面倒な条件を考える必要がなくなり、単純に縮約後のグラフの最小全域木のコストはいくらになるか、という問題に言い換えることができる。

なおSiとTiを縮約するという操作はSi-Ti間にコスト0の辺を加えると言い換えてもここでは問題がない。後の見通しがよくなるのでここでは後者のやり方を取る。そうすると、各クエリで求める必要があるのは「元のグラフにSi-Ti間のゼロコスト辺を加えたグラフの最小全域木（のコスト）」である。これは各クエリで毎回愚直に求める必要はなく、最初に元のグラフの最小全域木さえ求めておけば簡単に求めることができる。具体的には元のグラフの最小全域木のSi-Ti間にゼロコスト辺を足す。そうするとひとつ辺が余るので取り除いて全体の重みを小さくすることができるようになる。ここで取り除くべき辺は、取り除いても連結のままになる辺のうち、コストがもっとも大きいものである。「取り除いても連結のままになる辺」は初めの最小全域木のうちSiとTiの間にある辺、つまりSi-Tiのパス上にあるいずれかの辺である。Nが小さいのでこれを毎クエリごとにO(N)で求めても十分間に合う。これでO(NQ)で解ける。

感想

縮約、結構現れるテクっぽい

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip, std.regex;

immutable long INF = 1L << 59;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto G = new Tuple!(int, long)[][](N);
    foreach (i; 0..M) {
        s = readln.split.map!(to!int);
        G[s[0]-1] ~= tuple(s[1]-1, s[2].to!long);
        G[s[1]-1] ~= tuple(s[0]-1, s[2].to!long);
    }

    long mst_cost = 0;
    auto H = new Tuple!(int, long)[][](N);
    auto P = new Tuple!(int, long)[](N);
    auto D = new int[](N);
    auto used = new bool[](N);
    auto q = new BinaryHeap!(Array!(Tuple!(int, int, long)), "a[2] > b[2]")();
    q.insert(tuple(-1, 0, 0L));

    while (!q.empty) {
        auto t = q.front;
        auto from = t[0];
        auto cur = t[1];
        auto d = t[2];
        q.removeFront;
        if (used[cur]) continue;
        used[cur] = true;
        mst_cost += d;
        if (from != -1) {
            H[from] ~= tuple(cur, d);
            H[cur] ~= tuple(from, d);
        }
        foreach (m; G[cur]) {
            auto tar = m[0];
            auto nd = m[1];
            if (used[tar]) continue;
            q.insert(tuple(cur, tar, nd));
        }
    }

    void dfs(int n, int p, long c, int d) {
        P[n] = tuple(p, c);
        D[n] = d;
        foreach (to; H[n]) if (to[0] != p) dfs(to[0], n, to[1], d+1);
    }

    dfs(0, -1, 0, 0);


    auto Q = readln.chomp.to!int;
    while (Q--) {
        s = readln.split.map!(to!int);
        auto a = s[0]-1;
        auto b = s[1]-1;
        if (D[a] > D[b]) swap(a, b);
        long maxv = -1;
        while (D[b] > D[a]) {
            maxv = max(maxv, P[b][1]);
            b = P[b][0];
        }
        while (a != b) {
            maxv = max(maxv, P[a][1]);
            a = P[a][0];
            maxv = max(maxv, P[b][1]);
            b = P[b][0];
        }
        writeln(mst_cost - maxv);
    }
}