AOJ 2318: 舞台装置の魔女 / Set-constructing Witch

,

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

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;
}