けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Codeforces Global Round 12 E. Capitalism (R2700)

なんとなくできそうだけどできないみたいな問題だった。そうか、牛ゲーに帰着すれば明快だ...

問題概要

頂点数  N、辺数  M の連結グラフが与えられる。いくつかの辺は無向辺であり、いくつかの辺は有向辺である。

各頂点  v に 0 以上の整数値  a_{v} を割り振る方法のうち、

  •  \max_{v}a_{v} - \min_{v}a_{v}

の値が最大になるものを一つ求めよ (復元も要求)。そのような方法が存在しない場合はその旨を報告せよ。

  •  e = (u, v) が無向辺であるとき、 |a_{u} - a_{v}| = 1 を満たす
  •  e = (u, v) が有向辺であるとき、 a_{v} = a_{u} + 1 を満たす

制約

  •  1 \le N \le 200
  •  N-1 \le M \le 2000

考えたこと

まずグラフが二部グラフでないとダメである。以下、グラフは二部グラフであるものとして考える。

 e = (u, v) が無向辺であるとき、

 a_{u} - a_{v} = -1, 1

の二種類の値をとりうるが、ここではあえて

 a_{u} - a_{v} = -1, 0, 1

の三種類の値をとりうるものとして、解を求めてみる。このように緩和しても解が存在しない場合は No となる。このように緩和すると、条件は、

  •  a_{u} - a_{v} \le 1
  •  a_{v} - a_{u} \le 1

という 2 つの差分制約型の不等式で記述できる。さらに有向辺  e = (u, v) に対する条件も、

  •  a_{v} - a_{u} \le 1
  •  a_{u} - a_{v} \le -1

という 2 つの差分制約型の不等式と同値になる。以上から、問題で与えられた条件はすべて「差分制約系」で書けることとなった。牛ゲーに帰着できる形だ。

 {\rm argmin}_{v} a_{v} を固定する

 a_{v} が最小となる  v を固定して考えることにしよう。このとき、各頂点  t に対して、先述の差分制約系を満たしながら

 a_{t} - a_{v}

の最大値を求める問題となる。これは牛ゲーそのものである。具体的には

  • 無向辺  e = (u, v) に対しては、
    •  u から  v の方向に長さ 1 の辺
    •  v から  u の方向に長さ 1 の辺
  • 有向辺  e = (u, v) に対しては、
    •  u から  v の方向に長さ 1 の辺
    •  v から  u の方向に長さ -1 の辺

を張ってできるグラフにおいて、頂点  v を始点とする最短路問題を解けばよい。最短路の最大値が求める答えだ。以上のことを始点  v を動かして調べれば OK。結局全頂点を始点とした最短路問題を解くことになるので、Floyd--Warshall 法を用いるのが便利。

 a_{u} - a_{v} = 0 を認めたことについて

最後に、 |a_{u} - a_{v}| = 1 という制約に対して、 a_{u} - a_{v} = 0 となることを認めたことについて。

グラフが二部グラフであるとき、「牛ゲー」を解いて得られた解は、実際には  a_{u} = a_{v} となることはありえない。もしそうなるならば、二部グラフであることに反するからだ。もし

 a_{u} = a_{v} = k

となる 2 頂点  u, v が存在すると仮定すると、始点から頂点  u, v への最短路パスは、その本数はそれぞれ  kパリティが等しくなるはずである。よって、それらの最短路と辺 (u, v) とでできるサイクルに含まれる辺の本数が奇数になって矛盾である。

コード

以下の実装では二部グラフ判定に Union-Find を用いているため、計算量は  O(N^{3} + M\alpha(N)) となる。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { 
    if (a < b) { a = b; return 1; } 
    return 0; 
}
template<class T> inline bool chmin(T& a, T b) { 
    if (a > b) { a = b; return 1; } 
    return 0; 
}

struct UnionFind {
    vector<int> par;

    UnionFind() { }
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

const int INF = 1<<29;
int main() {
    auto solve = [&]() -> bool {
        int N, M;
        cin >> N >> M;
        UnionFind uf(N*2);
        vector<vector<int>> dp(N, vector<int>(N, INF));
        for (int i = 0; i < N; ++i) dp[i][i] = 0;
        for (int i = 0; i < M; ++i) {
            int u, v, c;
            cin >> u >> v >> c;
            --u, --v;
            uf.merge(u, v+N), uf.merge(v, u+N);
            if (c == 1) dp[u][v] = 1, dp[v][u] = -1;
            else dp[u][v] = dp[v][u] = 1;
        }
        for (int k = 0; k < N; ++k)
            for (int i = 0; i < N; ++i)
                for (int j = 0; j < N; ++j)
                    chmin(dp[i][j], dp[i][k] + dp[k][j]);

        // 二部グラフ判定, 負閉路存在判定
        for (int v = 0; v < N; ++v) {
            if (uf.issame(v, v+N)) return false;
            if (dp[v][v] < 0) return false;
        }

        // 牛ゲー
        int vmax = 0, pmax = 0;
        for (int s = 0; s < N; ++s) {
            int tmp = 0;
            for (int t = 0; t < N; ++t) chmax(tmp, dp[s][t]);
            if (chmax(vmax, tmp)) pmax = s;
        }
        cout << "YES" << endl << vmax << endl;
        for (int v = 0; v < N; ++v) cout << dp[pmax][v] << " ";
        cout << endl;
        return true;
    };
    if (!solve()) cout << "NO" << endl;
}