POJ 3228 - Gold Transportation

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

概要

N 個の街が M 本の道(双方向)で繋がれている． 金鉱も倉庫も街に存在し，金鉱からとれたすべての金を倉庫までトラックで運ぶ． 金鉱には金の量が，倉庫には倉庫の容量が設定されている．

トラックの運転手は bad temper なことで有名で，街から街へ移動するたびに休憩をとる． そこで，金を運ぶ際に通る道の長さの最大値を最小化したい． そのときの最小値を答える．

ただし，すべての金を倉庫まで運べないときは「No Solution」と出力する．

制約

解法

長さが K 以下の道のみを使って題意を満たせるかどうかを判定して，K について二分探索．

判定は，各連結成分の中で 金の量の合計 <= 倉庫の容量の合計 となっているかどうかを調べればいい．

 1 #include <cstdio>
 2 #include <vector>
 3 #include <queue>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 bool ok(const vector<vector<pair<int,int> > >& g, const vector<int>& gold, int K)
 8 {
 9   const int N = g.size();
10   vector<int> visited(N, false);
11   for (int i = 0; i < N; i++) {
12     if (visited[i]) {
13       continue;
14     }
15     queue<int> q;
16     q.push(i);
17     visited[i] = true;
18     int c = 0;
19     while (!q.empty()) {
20       const int n = q.front();
21       q.pop();
22       c += gold[n];
23       for (vector<pair<int,int> >::const_iterator it = g[n].begin(); it != g[n].end(); ++it) {
24         const int m = it->first;
25         const int d = it->second;
26         if (d <= K && !visited[m]) {
27           visited[m] = true;
28           q.push(m);
29         }
30       }
31     }
32     if (c > 0) {
33       return false;
34     }
35   }
36   return true;
37 }
38 
39 int main()
40 {
41   int N;
42   while (scanf("%d", &N) != EOF && N != 0) {
43     vector<int> gold(N, 0);
44     for (int i = 0; i < N; i++) {
45       int c;
46       scanf("%d", &c);
47       gold[i] += c;
48     }
49     for (int i = 0; i < N; i++) {
50       int c;
51       scanf("%d", &c);
52       gold[i] -= c;
53     }
54     vector<vector<pair<int,int> > > g(N);
55     int M;
56     scanf("%d", &M);
57     for (int i = 0; i < M; i++) {
58       int u, v, d;
59       scanf("%d %d %d", &u, &v, &d);
60       --u;  --v;
61       g[u].push_back(make_pair(v, d));
62       g[v].push_back(make_pair(u, d));
63     }
64 
65     static const int INF = 1000000;
66     int left = 0, right = INF;
67     while (left < right) {
68       const int mid = (left + right)/2;
69       if (ok(g, gold, mid)) {
70         right = mid;
71       } else {
72         left = mid+1;
73       }
74     }
75     if (left == INF) {
76       puts("No Solution");
77     } else {
78       printf("%d\n", left);
79     }
80   }
81   return 0;
82 }
poj/3228.cc