AOJ 2318: 舞台装置の魔女 / Set-constructing Witch
solution
Dijkstra法っぽい感じの動的計画法。 各魔女を作るのに必要な特別なグリーフシードの数だけ記憶していればよい。 $O(E \log N + \sum C_i)$。
まず魔女の作成可能性だけ考える。 法則$(S_1, S_2, \dots, S_c) \to G$があったとき、魔女$S_1, S_2, \dots, S_c$が全て作成可能なら魔女$G$を作成可能にしてよい。 制約「同じ種類の魔女を同時に複数のグリーフシードに入れることは出来ない」を無視してよいと言っていることに注意。 魔女$S_i$を作るのに別の魔女$S_j$を使うような場合が気になるが、魔女$S_j$を作る仮定に魔女$S_i$は出てこないとしてよい。 出てくる場合は魔女$S_j$は不要であったということであり、作る経路が縮むので必要となる特別なグリーフシードも減少することを覚えておく。
特別なグリーフシードの使用数の下限について。 上の議論を踏まえれば、法則$(S_1, S_2, \dots, S_c) \to G$で魔女$G$を作成するとき魔女$S_1, S_2, \dots, S_c$は独立に作成できる。 必要な特別なグリーフシードの数をそれぞれ$\mathrm{dp}_1, \mathrm{dp}_2, \dots, \mathrm{dp}_c$とすると、作り終えた分を横に取っておかなければならないので、適当に並べ変えた後$\max \{ \mathrm{dp}_1, \mathrm{dp}_2 + 1, \mathrm{dp}_3 + 2, \dots, \mathrm{dp}_c + (c-1) \}$個が$G$を作るのに必要な数。
$\mathrm{dp}_i$の値を決定していく順番は単純ではないが、上の操作の単調性によりDijkstra法のようにすれば正しく求まる。
implementation
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
constexpr int inf = 1e9+7;
int main() {
int n, e, t; scanf("%d%d%d", &n, &e, &t); -- t;
vector<bool> w(n); repeat (i, n) { int w_i; scanf("%d", &w_i); w[i] = w_i; }
vector<int> goal(e), cnt(e);
vector<vector<int> > src(e);
vector<vector<int> > use(n);
repeat (i, e) {
scanf("%d%d", &goal[i], &cnt[i]); -- goal[i];
src[i].resize(cnt[i]); repeat (j, cnt[i]) { scanf("%d", &src[i][j]); -- src[i][j]; }
for (int s : src[i]) use[s].push_back(i);
}
vector<int> cost(n, inf);
reversed_priority_queue<pair<int, int> > que;
repeat (i, n) if (w[i]) {
que.emplace(1, i);
}
auto use_law = [&](int j) {
vector<int> costs(src[j].size());
repeat (k, src[j].size()) {
costs[k] = cost[src[j][k]];
}
whole(sort, costs);
whole(reverse, costs);
int cost_i = 0;
repeat (k, costs.size()) {
setmax(cost_i, costs[k] + k);
}
int i = goal[j];
if (cost_i < cost[i]) {
que.emplace(cost_i, i);
}
};
while (not que.empty()) {
int cost_i, i; tie(cost_i, i) = que.top(); que.pop();
if (cost[i] <= cost_i) continue;
assert (cost[i] == inf);
cost[i] = cost_i;
for (int j : use[i]) {
cnt[j] -= 1;
if (cnt[j] == 0) {
use_law(j);
}
}
}
int result = cost[t];
if (result == inf) result = -1;
printf("%d\n", result);
return 0;
}