DDCC C. グラフいじり - Learning Algorithms

DDCC 2017 本戦 C. グラフいじり

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

感想

dfsの計算量を間違えていた。$\ O(m(n + m))\ $。これは$\ O(n^4)\ $なので、$\ TLE\ $する。仕方がないので無理やり通した。

解法

まずはある有向グラフが与えられたときに、それが条件（どのサイクルの距離の総和も$\ 0\ $であること）を満たしているかどうかを判定することを考える。条件を満たしているグラフの任意の異なる2点$\ S, T\ $を見ると、$\ S\ $から$\ T\ $に向かう任意のパスの距離はすべて一定になっているはずである。なぜなら、もし2つのパスが存在してその距離がそれぞれ$\ d_1, d_2\ (d_1 \neq d_2)\ $となっているならば、条件より存在する$\ T\ $から$\ S\ $へのある共通のパスを用いてサイクルを2つ作ると、これらの少なくとも一方の総和は$\ 0\ $でないので矛盾する。また、この距離を$\ d\ $とすると、$\ T\ $から$\ S\ $へのパスの距離は$\ -d\ $となっているはずである。そして逆に任意の2点についてこの距離の条件が成り立てば、条件を満たすことがわかる。これは簡単なdfsで求めることができる。計算量は$\ O(n)\ $である（これは嘘で、本当は$\ O(n + m) = O(m) = O(n^2)\ $）。

さて、次に長さを変える辺を一つ固定し、この繋いでいる頂点を$\ S \ $ -> $\ T\ $、その長さを$\ x\ $と仮定する。すると、まず必要条件として、上の条件と同じようなことを考えることができるはずであり、あるサイクルに関して総和が$\ 0\ $になるようにするための$\ x\ $が一意に定まるはずである。これを決めてしまえば、上で述べた判定によって、全体が条件を満たすかを判定すればよい。

従って、これをすべての辺についてチェックすればよい。この操作は$\ O(m)\ $でできるので、全体の計算量は$\ O(nm)\ $となるので十分高速である（これは嘘で、本当は$\ O(n^4)\ $なので、間に合わない）。

よって間に合わないことがわかるが、せっかく書いたので通したい。辺を順番に見ている場合でもほとんど通っているので、辺をランダムにシャッフルし、前半の$\ X\ $％だけ試す方針をとることにする。これはstd::shuffleを使うなどして実装する。辺が少ないときはすべて見てよいとし、辺数が$\ 50000\ $を超えるときは$\ 60\ $％、辺数が$\ 75000\ $を超えるときは$\ 35\ $％をみて、条件を満たすものが見つかるまで探索し、なければ即終了するという実装にすると、5回投げたら3回通るくらいの精度（？）になった。

実装

#include &quot;bits/stdc++.h&quot;
using namespace std;

#define mp make_pair

static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;

long long dist[303];
vector<pair<int, long long>> g[303];

struct edge {
        int a, b;
        long long cost;
};


void init() { for (int i = 0; i < 303; i ++) dist[i] = -INFL; }

bool check(int v, int from, int to, long long x, long long d) {
        dist[v] = d;
        for (auto e : g[v]) {
                int u = e.first, cost = e.second;
                if (from == v && to == u) {
                        assert(d == 0);
                        if (!check(u, from, to, x, d + x)) return false;
                } else if (dist[u] == -INFL) {
                        if (!check(u, from, to, x, d + cost)) return false;
                } else if (dist[u] != d + cost) { 
                        return false;
                }
        }
        return true;
}

long long get_x(int v, long long d) {
        dist[v] = d;
        for (auto e : g[v]) {
                int u =e.first, cost = e.second;
                if (dist[u] == -INFL) {
                        long long x = get_x(u, d + cost);
                        if (x != INFL) return x;
                } else if (dist[u] != d + cost) {
                        return d + cost - dist[u];
                }
        }
        return INFL;
}

int main() {
        int n, m;
        scanf(&quot;%d%d&quot;, &n, &m);
        vector<edge> es;
        for (int i = 0; i < m; i ++) {
                int a, b;
                long long c;
                scanf(&quot;%d%d%lld&quot;, &a, &b, &c);
                a --, b --;
                g[a].push_back(mp(b, c));
                es.push_back((edge) {a, b, c} );
        }

        //Randomly choose the edges
        random_device seed_gen;
        mt19937 engine(seed_gen());
        shuffle(es.begin(), es.end(), engine);

        for (int i = 0; i < m; i ++) {
                if (m > 50000) if (i > (m * 60) / 100) break;
                if (m > 75000) if (i > (m * 35) / 100) break;
                edge e = es[i];
                int v = e.a, u = e.b;
                long long cost = e.cost;
                init();
                dist[v] = 0;
                long long x = get_x(u, 0); 
                if (x == INFL) x = 0;
                init();
                bool ans = check(v, v, u, -x, 0);
                if (ans) return !puts(&quot;Yes&quot;);
        }
        return !puts(&quot;No&quot;);
}