TopCoder SRM584 Div1 Easy 250 Egalitarianism

概要

無向グラフが与えられる.

各頂点 $ u $ に値 $ a_u $ を, $\forall \{u, v\} \in E(G),\ | a_u - a_v | \le d $ という制約付きで割り振りたい.

$ | a_u - a_v | $ の最大値を最小化せよ. いくらでも大きく出来るときは $ -1 $.

制約

$ 1 \le n \le 50 $.

解法

超カンタンバージョンの牛ゲー. というか, グラフの直径を求めろという.

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 230.81 pts

int Egalitarianism::maxDifference( vector <string> g, int D ){
    const int n = size(g);
    vector<vector<int>> d(n, vector<int>(n, 1<<10));
    rep(i, n) d[i][i] = 0;
    rep(i, n) rep(j, n) if(g[i][j] == 'Y') d[i][j] = 1;
    rep(k, n) rep(i, n) rep(j, n) chmin(d[i][j], d[i][k] + d[k][j]);
    int res = 0;
    rep(i, n) rep(j, n) chmax(res, d[i][j]);
    if(res > (1<<10)-10) res = -1;
    else res *= D;
    return res;
}

// vim:set foldmethod=marker commentstring=//%s: