[AHOI2014/JSOI2014] 骑士游戏

GitHub跳转原题关系图返回列表

设 f[i] 表示杀死一只 i 号怪兽的最小体力，满足 f[i]=min(K_i, S_i+Σf[spawn])。先把法术攻击代价当作初值，再从已确定更小代价的子怪兽反向更新父怪兽。

OJ: luogu

题目 ID: P4042

难度:提高+/省选-

标签:图论最短路思维

日期: 2026-06-20 05:14

目录

  1. 题意
  2. 思路
    1. 关键观察
    2. 初始化为什么可以从法术攻击开始
    3. 为什么像 Dijkstra 一样做
    4. 维护什么量
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

面对一种怪兽 ii 时，有两种处理方式：

  1. 法术攻击：花 KiK_i，直接彻底消灭
  2. 普通攻击：花 SiS_i，但它会变出若干只新的怪兽

这些新怪兽也必须继续被清理。
现在只有一只 11 号怪兽出现，问最少要花多少体力才能把它和它衍生出来的所有怪兽全部消灭。

思路

先看一个更直观的小数据暴力：

cpp
#include <bits/stdc++.h>
using namespace std;

using i128 = __int128_t;

int n;
i128 normal_cost[25], magic_cost[25];
vector<int> spawn[25];
i128 dist_arr[25];

string to_string_i128(i128 x) {
    if (x == 0) {
        return "0";
    }

    bool neg = false;
    if (x < 0) {
        neg = true;
        x = -x;
    }

    string s;
    while (x > 0) {
        int digit = (int) (x % 10);
        s.push_back(char('0' + digit));
        x /= 10;
    }
    if (neg) {
        s.push_back('-');
    }
    reverse(s.begin(), s.end());
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        long long s, k;
        int r;
        cin >> s >> k >> r;
        normal_cost[i] = (i128) s;
        magic_cost[i] = (i128) k;
        spawn[i].clear();
        for (int j = 1; j <= r; j++) {
            int child;
            cin >> child;
            spawn[i].push_back(child);
        }
    }

    for (int i = 1; i <= n; i++) {
        dist_arr[i] = magic_cost[i];
    }

    // 更直接的小数据做法：
    // 反复使用方程
    // f[i] = min(法术攻击, 普通攻击 + 生成怪兽的总代价)
    // 直到没有任何值继续下降。
    bool changed = true;
    while (changed) {
        changed = false;

        for (int i = 1; i <= n; i++) {
            i128 cand = normal_cost[i];
            for (size_t j = 0; j < spawn[i].size(); j++) {
                cand += dist_arr[spawn[i][j]];
            }

            if (cand < dist_arr[i]) {
                dist_arr[i] = cand;
                changed = true;
            }
        }
    }

    cout << to_string_i128(dist_arr[1]) << '\n';

    return 0;
}

暴力其实就是把题意直接写成方程：

  • f[i]f[i] 表示杀死一只 ii 号怪兽的最小体力

那么：

  • 如果用法术攻击，代价是 KiK_i
  • 如果用普通攻击，代价是 Si+S_i + 生成出来的所有怪兽代价之和

所以有：

f[i]=min⁡(Ki,Si+∑f[child])f[i] = \min(K_i, S_i + \sum f[child])

brute.cpp 就是反复用这个式子去松弛，直到所有值都不再下降。

这个写法很好理解，但大数据下反复全扫会太慢。

关键观察

把式子换个方向看：

  • 子怪兽的代价确定之后，父怪兽用普通攻击的总代价也就确定了

也就是说，信息传播方向其实是：

  • 从"被生成的怪兽"反向流回"生成它的怪兽"

初始化为什么可以从法术攻击开始

对每种怪兽来说，法术攻击永远是一种合法方案。
所以一开始我们就知道一个上界：

  • f[i]⩽Kif[i] \leqslant K_i

于是可以先把：

  • f[i]=Kif[i] = K_i

当成初值。

如果后来发现：

  • Si+∑f[child]S_i + \sum f[child]

更小，就再把 f[i]f[i] 往下更新。

为什么像 Dijkstra 一样做

普通攻击方案的总代价是：

  • Si+∑f[child]S_i + \sum f[child]

注意这里 Si>0S_i > 0，而且每个 child 的代价也都是非负。
所以一个怪兽通过普通攻击得到的总代价，一定不会比它那些子怪兽的代价更小。

这说明"更小的答案"会先在子怪兽处出现，再逐步传回父怪兽。
因此可以像 Dijkstra 那样：

  1. 先确定当前代价最小的怪兽
  2. 用它去反向更新所有父怪兽

维护什么量

对每个怪兽 ii，维护：

  • dist[i]dist[i]：当前最优答案
  • sum_cost[i]sum\_cost[i]：如果走普通攻击，目前已经累计出的总代价
  • remain_need[i]remain\_need[i]：这个普通攻击方案里，还有多少个子怪兽的最终代价没确认

当某个子怪兽 uu 的最终代价确定后，就把它加进所有父怪兽的 sum_costsum\_cost。
如果某个父怪兽的所有子怪兽都处理完了，那么它的普通攻击方案总代价也就完整了，可以拿来更新答案。

这个过程可以用下面这张图来理解：

flowchart LR
  A["child 的最优代价确定"] --> B["加到 parent 的 sum_cost 里"]
  B --> C{"remain_need 是否归零?"}
  C -- 是 --> D["用 sum_cost 更新 dist[parent]"]

图里真正要看的，不是道路或最短路边，而是"一个普通攻击方案何时才算完整可用"。
只有它生成出来的所有怪兽代价都已经确定，这个方案才能真正参与比较。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200000 + 5;
const int MAXR = 1000000 + 5;

using i128 = __int128_t;

struct HeapNode {
    int u;
    i128 dist;

    bool operator < (const HeapNode &other) const {
        return dist > other.dist;
    }
};

int n;
i128 normal_cost[MAXN], magic_cost[MAXN];
i128 dist_arr[MAXN];   // 杀死一只 i 号怪兽的最小体力
i128 sum_cost[MAXN];   // 如果选择普通攻击，当前已经知道的总代价
int remain_need[MAXN]; // 这个普通攻击方案里，还有多少只后继怪兽代价没汇总完
bool vis[MAXN];

int head_rev[MAXN], to_rev[MAXR], nxt_rev[MAXR], rev_cnt;

void add_rev_edge(int child, int parent) {
    rev_cnt++;
    to_rev[rev_cnt] = parent;
    nxt_rev[rev_cnt] = head_rev[child];
    head_rev[child] = rev_cnt;
}

string to_string_i128(i128 x) {
    if (x == 0) {
        return "0";
    }

    bool neg = false;
    if (x < 0) {
        neg = true;
        x = -x;
    }

    string s;
    while (x > 0) {
        int digit = (int) (x % 10);
        s.push_back(char('0' + digit));
        x /= 10;
    }
    if (neg) {
        s.push_back('-');
    }
    reverse(s.begin(), s.end());
    return s;
}

void solve() {
    priority_queue<HeapNode> pq;

    for (int i = 1; i <= n; i++) {
        dist_arr[i] = magic_cost[i];
        if (remain_need[i] == 0 && sum_cost[i] < dist_arr[i]) {
            dist_arr[i] = sum_cost[i];
        }
        pq.push({i, dist_arr[i]});
    }

    while (!pq.empty()) {
        HeapNode cur = pq.top();
        pq.pop();

        int u = cur.u;
        if (vis[u]) {
            continue;
        }
        vis[u] = true;

        // 当子怪兽 u 的最优代价确定后，它会让一批“父怪兽”的普通攻击方案更便宜。
        for (int i = head_rev[u]; i != 0; i = nxt_rev[i]) {
            int parent = to_rev[i];
            remain_need[parent]--;
            sum_cost[parent] += dist_arr[u];

            if (remain_need[parent] == 0 && sum_cost[parent] < dist_arr[parent]) {
                dist_arr[parent] = sum_cost[parent];
                pq.push({parent, dist_arr[parent]});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    rev_cnt = 0;
    for (int i = 1; i <= n; i++) {
        head_rev[i] = 0;
        vis[i] = false;
    }

    for (int i = 1; i <= n; i++) {
        long long s, k;
        int r;
        cin >> s >> k >> r;

        normal_cost[i] = (i128) s;
        magic_cost[i] = (i128) k;
        sum_cost[i] = normal_cost[i];
        remain_need[i] = r;

        for (int j = 1; j <= r; j++) {
            int child;
            cin >> child;
            add_rev_edge(child, i);
        }
    }

    solve();
    cout << to_string_i128(dist_arr[1]) << '\n';

    return 0;
}

复杂度

设所有普通攻击生成关系的总数是：

  • R=∑RiR = \sum R_i

每个生成关系只会被处理一次，优先队列复杂度为：

  • O((N+R)log⁡N)O((N + R) \log N)

空间复杂度：

  • O(N+R)O(N + R)

总结

这题表面不像最短路，但本质上很像一类"反向更新"的最优值传播。

最关键的式子只有一个：

  • f[i]=min⁡(Ki,Si+∑f[child])f[i] = \min(K_i, S_i + \sum f[child])

一旦把它想清楚，再意识到信息是从子怪兽往父怪兽传，就能顺着写出整题。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析