DISCO presents ディスカバリーチャンネル コードコンテスト2017 本戦: C - グラフいじり

https://atcoder.jp/contests/ddcc2017-final/tasks/ddcc2017_final_c

問題概要

N頂点M辺の強連結な重み付き有向グラフが与えられる。ひとつの辺の重みを自由に変更できるとき、グラフのすべての単純サイクルについて、サイクル内に含まれる辺の重みの和が0となるようにすることができるか判定せよ。

N <= 300

M <= N2 - N

解法

ここの部分は以下の記事を言い換えてるだけなので、見ていない方はまずそちらから目を通すことをおすすめします。わかりやすいです。


まず辺の重みを変更できるという条件を一旦忘れて、辺の重みが全てそのままであるとき条件が満たせるかどうかを考える。これは実はDFS1回で判定可能である。具体的には通った辺の重みを足しながらDFSしていき、初訪問の頂点に当たったときはそのとき持っている合計重みをその頂点の値として記録しておく。訪問済みの頂点を再び訪れた場合、最初にその頂点に記録した値と現在持っている値が異なっていたら矛盾が生じるため条件は満たされない。逆にDFS全体でこのような矛盾が一度も生じなければ条件は満たされる。これはもし元の頂点に帰ってきたのであればどこかのサイクルをちょうど一回りしているはずで、サイクルをちょうど一回りしてるなら戻ってくるまでに取った重みの合計は0のはずなので、最初の値と同じでなければおかしい、という理屈である。

では辺をひとつ自由に変更できるという条件の元ではどうなるか。単純な方法として、変更する辺を総当たりするという方法が考えられる。この場合変更する辺eをひとつ決め、eが入っていく頂点を始点として上のDFSをやる。始点を固定する理由は、eを必ずサイクルの最後に訪れるようにするためである。上のDFSで矛盾が検出されるのはサイクルをちょうど一周したときで、このような始点の決め方をすればe上を移動した瞬間ちょうどサイクルができることになる。つまりeが関わっているサイクルすべてにおいて、eが最後の通る辺になる。これによって「もしe以外で矛盾が起きたらその時点でNG」「eで矛盾が起きたらちょうどよく調整が起きたことにして無視」という動きができる。これをすべての辺で試して、ひとつでもOKのものがあればOKということになる。

上の方法は辺の列挙にO(M), 1度のDFSでもO(M)かかりO(M2) = O(N4)となり間に合わない(DFSもO(M)なのは1度のDFSですべての辺を舐める必要があるため)。だがここである頂点vを始点とし、vに入る辺全部を変更候補として前段のDFSをやっても実は問題がない。なぜならこれらの辺は同じ単純サイクルには絶対に含まれないからである。ゆえにこのうちのひとつの辺の変更が他の辺の担当するサイクルに影響せず、独立に矛盾チェックを行うことができる。よって手続きとしては始点vを決めてDFSを行い、vに入ってくる辺で矛盾が起きたらカウントを+1し、カウントが2を超えたらNGとすればよい。もし無関係の辺で矛盾が起きたらこれまで同様即アウトとする。この方法では始点の総当たりでO(N), DFSでO(N2)の計O(N3)になるので通る。

感想

感覚でわかっても言葉で説明するのがむずい

コード (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, core.stdc.string;

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 (_; 0..M) {
        s = readln.split.map!(to!int);
        G[s[0]-1] ~= tuple(s[1]-1, s[2].to!long);
    }


    auto used = new bool[](N);
    auto cost = new long[](N);
    int cnt;

    bool dfs(int n, long c, int start) {
        if (used[n]) {
            if (cost[n] == c) return true;
            if (n != start) return false;
            if (cnt == 1) return false;
            cnt += 1;
            return true;
        }
        used[n] = true;
        cost[n] = c;
        foreach (e; G[n]) {
            if (!dfs(e[0], c+e[1], start)) return false;
        }
        return true;
    }

    foreach (start; 0..N) {
        used[] = false;
        cost[] = 0;
        cnt = 0;
        if (dfs(start, 0, start)) {
            writeln("Yes");
            return;
        }
    }

    writeln("No");
}