2020-12-08

Codeforces Global Round 12 E. Capitalism (R2700)

Codeforces CodeforcesCombined CodeforcesR2700 グラフ二部グラフ判定二部グラフ牛ゲー最適化テク:緩和しても良い Floyd-Warshall法最短路問題復元どれか1つ求める Yes/No判定問題必要条件を列挙したら十分条件になる個人的要復習差分制約系最大値と最小値の差を扱う問題ある量を固定して考える最大値の最大化

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

問題へのリンク

問題概要

頂点数 $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}$

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

無向辺に対しては、
- $u$ から $v$ の方向に長さ 1 の辺
- $v$ から $u$ の方向に長さ 1 の辺
有向辺に対しては、
- $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;
}

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

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

Codeforces Global Round 12 E. Capitalism (R2700)

問題概要

制約

考えたこと

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

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

コード