POJ 3169 - Layout

http://poj.org/problem?id=3169

概要

N 頭の牛が 1 .. N と順番に並んでいる． 同じ位置に複数の牛がいても構わない．

ML 個の「牛 A と牛 B の距離は D 以下」という制約と， MD 個の「牛 A と牛 B の距離は D 以上」という制約が与えられるので， それを満たすように並べたときの最大の牛 1 と牛 N の距離を答える．

ただし，制約を満たすように並べることができないときは -1，いくらでも牛 N を離すことができるときは -2 を答える．

制約

• 2 <= N <= 10^3
• 1 <= ML, MD <= 10^4
• 1 <= A < B <= N
• 1 <= D <= 10^6

解法

• i から i-1 へコスト 0 のエッジ
• ML に関して，A から B へコスト D のエッジ
• MD に関して，B から A へコスト -D のエッジ

というグラフを作ることで，ノード 1 からノード N への最短経路問題になる．

-2 のケースは緩和してもノード N の距離が ∞ であるときに対応し，-1 のケースは負閉路が存在するときに対応する．

負閉路の検出をしたいので，ベルマンフォードで解く．

 1 #include <iostream>
 2 #include <vector>
 3 using namespace std;
 4 
 5 struct edge
 6 {
 7   int u, v, c;
 8   edge(int x, int y, int z) : u(x), v(y), c(z) {}
 9 };
10 
11 int main()
12 {
13   int N, ML, MD;
14   cin >> N >> ML >> MD;
15   vector<edge> es;
16   for (int i = 1; i < N; i++) {
17     es.push_back(edge(i, i-1, 0));
18   }
19   for (int i = 0; i < ML; i++) {
20     int u, v, c;
21     cin >> u >> v >> c;
22     --u;  --v;
23     es.push_back(edge(u, v, c));
24   }
25   for (int i = 0; i < MD; i++) {
26     int u, v, c;
27     cin >> u >> v >> c;
28     --u;  --v;
29     es.push_back(edge(v, u, -c));
30   }
31 
32   static const long long INF = 1LL<<50;
33   vector<long long> dist(N, INF);
34   dist[0] = 0;
35   for (int i = 0; i < N; i++) {
36     for (vector<edge>::const_iterator it = es.begin(); it != es.end(); ++it) {
37       dist[it->v] = min(dist[it->v], dist[it->u] + it->c);
38     }
39   }
40   for (vector<edge>::const_iterator it = es.begin(); it != es.end(); ++it) {
41     if (dist[it->u] + it->c < dist[it->v]) {
42       cout << "-1" << endl;
43       return 0;
44     }
45   }
46   if (dist[N-1] == INF) {
47     cout << "-2" << endl;
48   } else {
49     cout << dist[N-1] << endl;
50   }
51   return 0;
52 }