PKU POJ 3169 Layout - しおしおたのブログ

問題概要

N匹の牛を飼っている。
牛は1〜N番目の牛まで順番に並んでいる。
いくつかの組み合わせについて、その牛同士の距離について、上限あるいは下限が与えられる。

実現できる最後の牛と最初の牛の最大の距離を求めよ。
ただし、そのような並び方がない場合は-1, 最大距離がどこまでも伸ばせる場合は、-2を答えよ。
牛同士は同じ場所にも立てる。

解法

ベルマンフォード。

なぜ最短経路問題なのか。

最短経路問題とは、全てのエッジについて、
d[i] + c >= d[j] (iからjに伸びるコストcのエッジ, d[i]はi番目のノードの始点からの最短距離)
という不等式を満たす、d[s] = 0 (sは始点) とした時の、
全てのノードiについてのd[i]の最大値を求める問題である。

今回の問題を最短経路問題のような不等式にしてみる。

d[i]を最初の牛からの距離とする。

牛i, i+1について、牛は順番に並んでることから、
- d[i] <= d[i+1]
牛i, jについて上限が決まってる場合、上限の距離をcとすると、
- d[i] + c >= d[j] ( j > i )
牛i, jについて下限が決まってる場合、下限の距離をcとすると、
- d[i] + c <= d[j] (j > i)

となる。
最短経路問題に当てはめるために式を変形すると、

d[i+1] + 0 >= d[i]
d[i] + c >= d[j]
d[j] - c >= d[i]

と変形できる。
そして、始点は最初の牛にするので、

d[0] = 0

よって、これらの式を全て満たす最大のd[N-1]をベルマンフォードで求めることができる。
最大距離が無限の場合は、d[N-1]がINFのまま、
解がない場合は、ベルマンフォードの性質から負のサイクルを検出できる。
負のサイクルを持つということは、どこまでもd[i]の値が小さくなる、詰まるころ満たす値が存在しない
つまるところ、解がない、ということになる。

ソース

#include<iostream>
#include<algorithm>
#include<vector>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)

using namespace std;
const int INF = 1000000000;
const int N = 1009;

struct Edge{
  int from, to, cost;
};

int d[N], n;

int bellman_ford(vector<Edge> &E, int s){
  rep(i, N)d[i] = INF;
  d[s] = 0;
  rep(i, n){
    rep(j, E.size()){
      Edge e = E[j];
      if(d[e.from] != INF && d[e.to] > d[e.from] + e.cost){
        d[e.to] = d[e.from] + e.cost;
        if(i == n-1)return -1;
      }
    }
  }
  if(d[n-1] >= INF){
    return -2;
  }
  return d[n-1];
}

int main(){
  int L, D;
  cin >> n >> L >> D;
  vector<Edge> E;
  rep(i, n-1){
    E.push_back((Edge){i+1, i+0, 0});
  }
  rep(i, L){
    int from, to, c;
    cin >> from >> to >> c;
    if(to < from)swap(from, to);
    E.push_back((Edge){from-1, to-1, c});
  }
  rep(i, D){
    int from, to, c;
    cin >> from >> to >> c;
    if(to < from)swap(from, to);
    E.push_back((Edge){to-1, from-1, -c});
  }
  cout << bellman_ford(E, 0) << endl;;
  return 0;
}