蟻本 p104 Layout（牛ゲーとベルマンフォード法）

問題（ざっくり）

1〜Nまで番号のついた牛がいる
牛は番号順に並んでいる
仲良しの牛a, bは距離d1以内に並べる
中が悪い牛c, dは距離d2以上離して並べる
1番目の牛とN番目の牛の距離の最大値を求めよ。
そのような並び方が存在しない場合は-1, いくらでも離せる場合は-2を出力

まずはベルマンフォード法を確認する

ベルマンフォード法を使って解くので、まずはこれを理解する。
ベルマンフォード法に関しての解説はこちらの記事が分かりやすかった。 2, 3回ほど以下の記事を行ったり来たりしながら、ゆっくり読むとだいたい理解できた。

AOJの問題が練習にちょうどいいので、まずはこれをベルマンフォード法で解く

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_B&lang=jp

※以下のコードはコーナーケースでバグっている可能性がありますのでコピペ利用は自己責任でお願いします

#include <bits/stdc++.h>
using namespace std;
const int IINF = 0x3f3f3f3f;  // 2倍しても負にならない
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
struct Edge {
  int from, to, cost;
  Edge(int f, int t, int c) : from(f), to(t), cost(c) {}
};

int main() {
  int nv, ne, start;  // 頂点数, 辺数, スタート位置
  cin >> nv >> ne >> start;

  vector<Edge> es;  // 辺の集合
  int d[nv];        // 最短距離

  // 最短距離を初期化
  for (int i = 0; i < nv; i++) {
    d[i] = IINF;
  }
  d[start] = 0;

  // 辺を入力
  for (int i = 0; i < ne; i++) {
    int x, y, cost;
    cin >> x >> y >> cost;
    es.push_back(Edge(x, y, cost));
  }

  // ベルマンフォード
  for (int i = 0; i < nv; i++) {
    // 最短経路更新
    bool updated = false;
    for (Edge e : es) {
      if (d[e.from] != IINF && d[e.to] > d[e.from] + e.cost) {
        d[e.to] = d[e.from] + e.cost;
        updated = true;
      }
    }
    // 更新がなければ抜ける
    if (!updated) {
      break;
    }
    // 負閉路検出
    if (i == nv - 1) {
      cout << "NEGATIVE CYCLE" << endl;
      return 0;
    }
  }

  for (int i = 0; i < nv; i++) {
    if (d[i] == IINF) {
      cout << "INF" << endl;
    } else {
      cout << d[i] << endl;
    }
  }
}

牛ゲーの考え方

ei1333.github.io 以下はこちらのページから引用した解説。これが一番分かりやすかった。（とは言っても、理解するのにけっこう苦労した。）

単一始点最短路は特殊な線形計画問題の双対である(いわゆる牛ゲー)。

頂点 s から頂点 v までの最短経路を f ( v ) とする。グラフに負閉路がなければ f(s) = 0 である。また頂点 u から v へ向かう重み w の辺が存在するとき f ( u ) + w ≥ f ( v ) が成立する。言い換えれば, 頂点 v には最大でも f ( u ) + w のコストで到達可能を意味している。

最短路問題を解くことで各 v について f ( v ) がとりうる最大の値を求めることができる。つまり f ( v ) の最大値を求める問題が最短路問題に対応する。

すべての制約が変数+定数≧変数の形で表される線形計画問題は, 対応するグラフ上での最短路問題を解くことで求めることが出来る。 f ( u ) + w ≥ f ( v ) が成立するとき, 頂点 u から頂点 v へ向かう重み w の辺を張れば良い。

以下の部分が牛ゲーのミソだと思ってる

つまり f(v) の最大値を求める問題が最短路問題に対応する。

実際に問題を解く時は、以下の部分を問題文から読み解くのが大切。

すべての制約が変数+定数≧変数の形で表される線形計画問題は, 対応するグラフ上での最短路問題を解くことで求めることが出来る。

牛ゲーの実装

というわけで、以下が実装。

制約を定式化する
定式化した制約を辺として受け取る
ベルマンフォード法適用

という感じで解ける

#include <bits/stdc++.h>
using namespace std;
const int IINF = 0x3f3f3f3f;  // 2倍しても負にならない
struct Edge {
  int from, to, cost;
  Edge(int f, int t, int c) : from(f), to(t), cost(c) {}
};

// ベルマンフォード法
// 負閉路ありならfalse, それ以外はtrueを返す
bool bf(int n, int start, vector<Edge> es, int d[]) {
  // 最短距離を初期化
  for (int i = 0; i < n; i++) {
    d[i] = IINF;
  }
  d[start] = 0;

  // ベルマンフォード
  for (int i = 0; i < n; i++) {
  // 最短経路算出
    bool updated = false;
    for (auto e : es) {
      if (d[e.from] != IINF && d[e.to] > d[e.from] + e.cost) {
        d[e.to] = d[e.from] + e.cost;
        updated = true;
      }
    }
    // 更新されていないなら終了
    if (!updated) {
      break;
    }
    // 負閉路検出
    if (i == n - 1) {
      return false;
    }
  }

  return true;
}

int main() {
  int n, ml, md;
  cin >> n >> ml >> md;

  vector<Edge> es;  // 辺の集合
  int d[n];         // 最短距離

  // d[i+1] + 0 >= d[i] の制約を満たす辺を追加
  for (int i = 0; i < n - 1; i++) {
    es.push_back(Edge(i + 1, i, 0));
  }

  // d[al] + dl >= d[bl] の制約を満たす辺を追加
  for (int i = 0; i < ml; i++) {
    int al, bl, dl;
    cin >> al >> bl >> dl;
    al--, bl--;
    es.push_back(Edge(al, bl, dl));
  }

  // d[bd] + (-dd) >= d[ad] の制約を満たす辺を追加
  for (int i = 0; i < md; i++) {
    int ad, bd, dd;
    cin >> ad >> bd >> dd;
    ad--, bd--;
    es.push_back(Edge(bd, ad, -dd));
  }

  if (bf(n, 0, es, d)) {
    if (d[n - 1] == IINF) {
      cout << -2 << endl;
    } else {
      cout << d[n - 1] << endl;
    }
  } else {
    cout << -1 << endl;
  }
}

nakashiiiの自由帳

自由に書きます

蟻本 p104 Layout（牛ゲーとベルマンフォード法）

問題（ざっくり）

まずはベルマンフォード法を確認する

牛ゲーの考え方

牛ゲーの実装