[AHOI2014/JSOI2014]骑士游戏

思博贪心题写了一个半小时没救了，我也没看出这是一个\(spfa\)来啊

设\(dp_i\)表示彻底干掉第\(i\)只怪物的最小花费，一个非常显然的事情，就是对于\(k_i\)值最小的怪物满足\(dp_i=k_i\)

非常好理解，反正到最后都要干掉这个怪物，何必再把它干成别的怪物

于是我们按照\(k_i\)的值先排序一下，另外维护一个小根堆

如果堆里没有点或者堆顶的\(dp\)值比当前的\(k\)要大，我们直接令当前当前\(k_i\)值最小的点\(i\)的\(dp_i=k_i\)，之后遍历所有能到达点\(i\)的点\(v\)，令\(s_v+=dp_i\)，如果发现点\(v\)的所有出边都被遍历了一遍，我们就令\(dp_v=\min(s_v,k_v)\)，同时把这个点加入堆中

如果堆里有点且堆顶的\(dp\)小于于当前\(k\)，就直接拿堆顶来更新

考虑这个做法的正确性，显然当前堆中没有节点的时候，图中任意一个点不可能只分解成已经处理好\(dp_i\)的点，于是我们必须引入剩下的\(k\)值最小的点

或者把堆中没有点的情况视为初始情况，可能这样更好理解

代码

#include <bits/stdc++.h>

#define re register

#define LL long long

#define mp std::make_pair

#define min(a, b) ((a) < (b) ? (a) : (b))

const int maxn = 2e5 + 5;

struct E {

    int v, nxt;

} e[1000005];

LL dp[maxn], s[maxn], w[maxn];

int head[maxn], vis[maxn], c[maxn], p[maxn];

int n, num, top;

inline LL read() {

    LL x = 0;

    char c = getchar();

    while (c < '0' || c > '9') c = getchar();

    while (c >= '0' && c <= '9') x = (x << 3ll) + (x << 1ll) + c - 48, c = getchar();

    return x;

}

typedef std::pair<LL, int> pii;

std::priority_queue<pii, std::vector<pii>, std::greater<pii> > q;

inline int cmp(int a, int b) { return s[a] < s[b]; }

inline void del(int x) {

    vis[x] = 1;

    for (re int i = head[x]; i; i = e[i].nxt) {

        if (vis[e[i].v])

            continue;

        w[e[i].v] += dp[x];

        c[e[i].v]--;

        if (!c[e[i].v])

            vis[e[i].v] = 1, dp[e[i].v] = min(w[e[i].v], s[e[i].v]), q.push(mp(dp[e[i].v], e[i].v));

    }

}

inline void add(int x, int y) {

    e[++num].v = y;

    e[num].nxt = head[x];

    head[x] = num;

}

int main() {

    n = read();

    for (re int x, i = 1; i <= n; i++) {

        w[i] = read(), s[i] = read(), c[i] = read();

        for (re int j = 1; j <= c[i]; j++) x = read(), add(x, i);

    }

    for (re int i = 1; i <= n; i++) p[i] = i;

    std::sort(p + 1, p + n + 1, cmp);

    int now = 1, tot = 0;

    while (tot < n) {

        while (vis[p[now]]) ++now;

        if (!q.empty() && (q.top().first < s[p[now]] || now > n))

            tot++, del(q.top().second), q.pop();

        else

            tot++, dp[p[now]] = s[p[now]], del(p[now++]);

    }

    printf("%lld\n", dp[1]);

    return 0;

}

巴特西

[AHOI2014/JSOI2014]骑士游戏

最新文章

热门文章