AOJ 2318 - Set-constructiong Witch

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2318

解法

魔女 i を作るのに必要なグリーフシードの数を dist[i] で表すと， 合成法則 G = S_1 + ... + S_c から， dist[G] は dist[S_1], ..., dist[S_c] を降順に並べてから max(dist[S'_1] + 0, ..., dist[S'_c] + c-1) で得られる．

そこで，合成法則に従って枝を張ったグラフを考える． dist[i] を

dist[i] = W_i ? 1 : INF

と初期化し，ベルマン・フォード法の要領で緩和して最終的な dist[T] が答えになる．

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <functional>
 5 using namespace std;
 6 static const int INF = 10000000;
 7 
 8 pair<vector<int>, bool>
 9 bellman_ford(const vector<vector<vector<int> > >& rules, const vector<int>& seed)
10 {
11   const int N = seed.size();
12   vector<int> dist(N, INF);
13   for (int i = 0; i < N; i++) {
14     if (seed[i]) {
15       dist[i] = 1;
16     }
17   }
18 
19   for (int i = 0; i < N; i++) {
20     for (int u = 0; u < N; u++) {
21       for (vector<vector<int> >::const_iterator it = rules[u].begin(); it != rules[u].end(); ++it) {
22         vector<int> v;
23         for (vector<int>::const_iterator jt = it->begin(); jt != it->end(); ++jt) {
24           v.push_back(dist[*jt]);
25         }
26         sort(v.begin(), v.end(), greater<int>());
27         int d = 0;
28         for (vector<int>::const_iterator jt = v.begin(); jt != v.end(); ++jt) {
29           d = max(d, int(*jt + (jt - v.begin())));
30         }
31         dist[u] = min(dist[u], d);
32       }
33     }
34   }
35 
36   for (int u = 0; u < N; u++) {
37     for (vector<vector<int> >::const_iterator it = rules[u].begin(); it != rules[u].end(); ++it) {
38       vector<int> v;
39       for (vector<int>::const_iterator jt = it->begin(); jt != it->end(); ++jt) {
40         v.push_back(dist[*jt]);
41       }
42       sort(v.begin(), v.end(), greater<int>());
43       int d = 0;
44       for (vector<int>::const_iterator jt = v.begin(); jt != v.end(); ++jt) {
45         d = max(d, int(*jt + (jt - v.begin())));
46       }
47       if (d < dist[u]) {
48         return make_pair(dist, false);
49       }
50     }
51   }
52   return make_pair(dist, true);
53 }
54 
55 int main()
56 {
57   int N, E, T;
58   cin >> N >> E >> T;
59   --T;
60   vector<int> seed(N);
61   for (int i = 0; i < N; i++) {
62     cin >> seed[i];
63   }
64   vector<vector<vector<int> > > rules(N);
65   for (int i = 0; i < E; i++) {
66     int g, c;
67     cin >> g >> c;
68     --g;
69     vector<int> r(c);
70     for (int j = 0; j < c; j++) {
71       cin >> r[j];
72       --r[j];
73     }
74     rules[g].push_back(r);
75   }
76 
77   const pair<vector<int>, bool> r = bellman_ford(rules, seed);
78   if (r.second && r.first[T] < INF) {
79     cout << r.first[T] << endl;
80   } else {
81     cout << "-1" << endl;
82   }
83   return 0;
84 }