牛ゲー

概要

\(N\) 個の変数 \(x_i\), \(M\) 個の 差分制約式(difference constraints) \(x_j - x_i \le b_k\) の元で、2つの変数からなる式 \(x_t - x_s\) を最大化する問題。 この問題は通称「牛ゲー」と呼ばれている。

この問題は 2頂点間の最短経路問題 の双対問題であり、 Bellman-Ford Algorithm で解くことができる。

変数 \(x_i\) を 頂点 \(v_i\) に対応させ、差分制約式 \(x_j - x_i \le b_k\) を 重み \(b_k\) を持つ \(v_i\) から \(v_j\) への有向辺に対応させた グラフを構築する。
このグラフ上で、 \(v_s\) を始点として \(v_t\) への最短路を求める。

負閉路がある場合は解なし。
それ以外の場合であれば 頂点 \(v_s\) からの 頂点 \(v_t\) までの最短距離が \(x_t - x_s\) の最大値と一致する。
頂点 \(v_s\) から 頂点 \(v_t\) まで到達できない場合は \(x_t - x_s\) はいくらでも大きくできることになる。

計算量

\(O(NM)\)

実装

INF = 10**9
def calc(N, E, s):
    G = [[] for i in range(N)]
    for a, b, d in E:
        # x_a - x_b <= d
        G[b].append((a, d))

    INF2 = INF**2
    dist = [INF2] * N
    dist[s] = 0
    update = 1
    for _ in range(N):
        update = 0
        for v in range(N):
            for w, d in G[v]:
                if dist[v] + d < dist[w]:
                    dist[w] = dist[v] + d
                    update = 1
        if not update:
            break
    else:
        return None
    for i in range(N):
        dist[i] = min(dist[i], INF)
    # dist[i]: the maximum value of (x_i - x_s)
    return dist

N = 3
# x_1 - x_0 <= 3
# x_2 - x_1 <= 5
# x_2 - x_0 <= 10
E = [(1, 0, 3), (2, 1, 5), (2, 0, 10)]
print(calc(N, E, 0))
# => "[0, 3, 8]"

Verified

  • AOJ: "0304: School Cafeteria": source (Python3, 0.41sec)

戻る