骑士游戏

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

把 f[i]=min(K_i, S_i+Σf[son]) 看成超图上的最短路:全部先取法术代价 K_i,再沿反向边把「变便宜了多少」SPFA 式地推给会产生它的怪兽,收敛到最低不动点。

OJ: roj

题目 ID: 1722

难度:提高+/省选-

标签:图论最短路SPFApython

创建: 2026-10-07 18:42

更新: 2026-10-07 18:42

形式化题目

有 NN 种怪兽,编号 1∼N1 \sim N。第 ii 种怪兽有两条处置路线:

  • 普通攻击:消耗 SiS_i 体力把它"打死",但它死后会立刻产生 RiR_i 只新怪兽, 编号为给定的 vi,1,…,vi,Riv_{i,1}, \dots, v_{i,R_i}(编号可重复,同一编号可以出现多次);
  • 法术攻击:消耗 KiK_i 体力把它彻底消灭,不产生任何新怪兽。

11 号怪兽入侵了村庄,其余怪兽只能由它衍生。求消灭村庄里所有怪兽所需的最小总体力。

注意"普通攻击"并不减少怪兽总量(一只换成 RiR_i 只,而 Ri⩾1R_i \geqslant 1), 所以它唯一的用处是把一只怪兽"拆"成更便宜的一批;每次普通攻击都是加体力, 不存在"打一下反而赚了"的负代价边。

正解

思路

先写出方程。 每只怪兽的处置彼此独立(11 号衍生出的怪兽之间互不影响, 同时出现的同一编号怪兽也各自独立),所以可以为每种怪兽单独定义一个量:

fi=彻底消灭一只 i 号怪兽以及它衍生出的一切所需的最小体力.f_i = \text{彻底消灭一只 } i \text{ 号怪兽以及它衍生出的一切所需的最小体力}.

一只 ii 号怪兽只有两种走法,取较小的那个:

fi=min⁡(Ki,  Si+∑j=1Rifvi,j).(1)f_i = \min\Bigl(K_i,\; S_i + \sum_{j=1}^{R_i} f_{v_{i,j}}\Bigr). \tag{1}

样例可以验算:f3=min⁡(13,1+f4+f2)=min⁡(13,1+6+5)=12f_3 = \min(13, 1 + f_4 + f_2) = \min(13, 1+6+5) = 12, f2=min⁡(5,3+f2)=5f_2 = \min(5, 3 + f_2) = 5(22 号自环,普通攻击永远不划算), f1=min⁡(27,4+2f2+f3)=min⁡(27,4+10+12)=26f_1 = \min(27, 4 + 2f_2 + f_3) = \min(27, 4+10+12) = 26,与样例输出一致。

难点在于它不是递推。 (1) 式右端依赖别的 ff,而这些依赖关系可能成环: 22 号怪兽死后会产生 22 号自己(题面明说"一个怪兽可能经过若干次普通攻击后变回一个或更多同样的怪兽"), 样例里 1→3→2→21 \to 3 \to 2 \to 2 就是一条环。所以不能按拓扑序一遍算完, 更不能天真地"遇到环就放弃"。

为什么一定有解、解又是什么。 两条关键性质:

  1. 上界存在。 fi⩽Kif_i \leqslant K_i 恒成立——法术攻击总是合法的,直接把它杀干净即可。 于是把所有 fif_i 都取成 KiK_i,得到的是合法解的一个上界。

  2. 单调性。 (1) 式右端关于每个 ff 单调不减。于是把它看成算子 TT, 从 f(0)=Kf^{(0)} = K 出发反复做 f(t+1)=T(f(t))f^{(t+1)} = T(f^{(t)}),序列单调不增且有下界, 必然收敛到最小不动点 f∗f^*,而 f∗f^* 就是要的答案:

    • 任何真实策略的代价都满足 (1) 式(策略要么一次法术杀掉,要么先普通攻击再分别处理衍生怪), 即每个合法策略的代价向量都是 TT 的一个不动点(或前不动点),故 ⩾f∗\geqslant f^*;
    • 反过来,f∗f^* 是 (1) 式的最小解,按 f∗f^* 里取到 min⁡\min 的那一支构造策略即为合法策略, 代价恰好是 f1∗f^*_1。

这就是"最短路"视角:ff 是这张超图(一条"边"从 ii 连向 RiR_i 个儿子,代价 SiS_i) 上的最短距离,环只是说明图不是 DAG,用 Bellman-Ford / SPFA 那套松弛照样能求。

朴素迭代慢在哪。 直接每轮全量扫一遍所有怪兽、把 (1) 式重算一次, 每轮代价 O(N+∑Ri)O(N + \sum R_i),最坏要迭代很多轮。真正的浪费是:绝大多数怪兽的 ff 这一轮根本没变, 而某个 fuf_u 变了以后,受影响的只有"会产生 uu 的那些怪兽"——它们的 ∑fson\sum f_{son} 恰好少了 Δ\Delta。

把影响面收窄。 维护

sumi=Si+∑j=1Rifvi,j,fi=min⁡(Ki,sumi),\mathrm{sum}_i = S_i + \sum_{j=1}^{R_i} f_{v_{i,j}}, \qquad f_i = \min(K_i, \mathrm{sum}_i),

并为每个怪兽 uu 记一份反向表:哪些怪兽的死亡清单里出现了 uu(这些怪兽叫 uu 的父亲)。 于是一条松弛规则就够了:

若 fuf_u 下降了 dd,则对每个父亲 pp:sump−=d\mathrm{sum}_p \mathrel{-}= d; 若这时 sump<fp\mathrm{sum}_p < f_p,就把 fpf_p 降到 sump\mathrm{sum}_p,并继续把 pp 的下降量往外传。

初始状态与队列。 取 fi=Kif_i = K_i、sumi=Si+∑Kvi,j\mathrm{sum}_i = S_i + \sum K_{v_{i,j}}; 凡是 sumi<fi\mathrm{sum}_i < f_i 的怪兽(普通攻击当场就更便宜)先入队,作为第一批"下降源"。 之后队列里存的是"ff 刚变小的怪兽",出队时把它攒下的下降量 dd 推给所有父亲。 这正是一遍 SPFA:每个 fif_i 只降不升,每次下降至少 11(都是整数),故算法必然终止。

两个实现细节。

  • 攒量而不是丢量。 同一只怪兽可能在出队前被连续降了多次。 给每个点配一个 pending[i],每次下降就累加进去,出队时一次性推给父亲; 否则后一次下降量会被前一次覆盖,答案偏大。同一个点还在队列里时不要重复入队(inq 标记)。
  • 中间量会爆 long long。 fi⩽Ki⩽5×1014f_i \leqslant K_i \leqslant 5 \times 10^{14},但 sumi\mathrm{sum}_i 可能到 ∑Ri×5×1014=5×1020\sum R_i \times 5 \times 10^{14} = 5 \times 10^{20}, 远超 long long 的 9.2×10189.2 \times 10^{18}。C++ 里把 sum 声明成 __int128 (只做加法和与 f 的比较,不参与输出),f 保持 long long。 不能简单地把 sum 截断饱和:ff 下降后 sum 会一路减回去,截断会丢掉这个减量。 Python 整数无上限,无需处理。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 18:42
# update_at: 2026-10-07 18:42

import sys
from collections import deque

# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type Rev = list[list[int]]  # rev[u] = 会产生 u 号怪兽的那些怪兽编号


def settle(n: int, rev: Rev, dp: list[int], sump: list[int], pending: list[int]) -> None:
    """把"某只怪兽变便宜了"沿反向边不断推给会产生它的怪兽,直到没人还能变便宜。

    dp[i] = 彻底消灭一只 i 及其衍生怪的最小体力,初值取法术攻击 K_i;
    sump[i] = S_i + Σ dp[son] 是普通攻击路线的当前代价。
    谁出队就把攒下的下降量 d 交给父亲们,父亲重算后可能继续下降(怪兽可能变回自己,故有环)。
    """
    inq = bytearray(n + 1)  # inq[i]:i 是否已在队列里,避免重复入队
    q = deque()
    for i in range(1, n + 1):  # 一开始就"普通攻击更便宜"的怪兽先入队
        if sump[i] < dp[i]:
            pending[i] += dp[i] - sump[i]
            dp[i] = sump[i]
            inq[i] = 1
            q.append(i)

    while q:
        u = q.popleft()
        inq[u] = 0
        d = pending[u]
        pending[u] = 0
        if not d:
            continue
        for p in rev[u]:  # p 会产生 u,u 便宜了 p 的普通攻击也跟着便宜
            sump[p] -= d
            if sump[p] < dp[p]:
                pending[p] += dp[p] - sump[p]
                dp[p] = sump[p]
                if not inq[p]:
                    inq[p] = 1
                    q.append(p)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)

    s = [0] * (n + 1)  # s[i]:普通攻击 i 消耗的体力
    k = [0] * (n + 1)  # k[i]:法术攻击 i 消耗的体力
    rev: Rev = [[] for _ in range(n + 1)]
    for i in range(1, n + 1):
        s[i], k[i] = next(data), next(data)
        r = next(data)  # 题面的 R_i:i 死亡后产生的新怪兽个数
        for _ in range(r):
            rev[next(data)].append(i)  # 反过来记:父亲 i 会产生这个孩子

    sump = s[:]  # 普通攻击的 S_i 部分;Σ dp[son] 部分此时 dp 还是 K
    for u in range(1, n + 1):
        ku = k[u]
        for p in rev[u]:
            sump[p] += ku

    dp = k[:]  # 所有怪兽先假设用法术攻击,再让松弛把更便宜的方案找出来
    settle(n, rev, dp, sump, [0] * (n + 1))

    print(dp[1])  # 只有 1 号怪兽入侵村庄


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 18:42
 * update_at: 2026-10-07 18:42
 */
// main.cpp:骑士游戏,在"怪兽产生的怪兽"这张超图上求最小体力,用 SPFA 式松弛求解。
// 设 dp[i] = 彻底消灭一只 i 号怪兽(连同它衍生出的一切)所需的最小体力,则
//     dp[i] = min( K_i , S_i + Σ dp[son] )
// 右边依赖别的 dp,还可能有环(怪兽可以变回自己),于是把每个 i 都初始化成 K_i,
// 谁变小就把"变小了多少"沿反向边推给产生它的怪兽,重新结算一次它的 Σ dp[son]。
// 与 main.py 同一算法:同样的反向边 + 同样的 delta 传播。

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

typedef long long ll;

const int MAXN = 200005;      // 怪兽种数上限 N <= 2e5
const int MAXM = 1000005;     // ΣR_i <= 1e6,反向边条数就是它

int N;                        // 怪兽种数
ll S[MAXN];                   // S[i]:普通攻击 i 号怪兽消耗的体力
ll K[MAXN];                   // K[i]:法术攻击 i 号怪兽消耗的体力
int st[MAXN];                 // st[i]:i 号怪兽的衍生怪编号在 sons[] 里的起始位置(前缀和)
int sons[MAXM];               // 所有衍生怪编号按父亲分组平铺存放,编号用 int 足够(<= 2e5)

int head[MAXN];               // head[u]:反向边链表头,链上每条边指向"会产生 u 的怪兽"
int nxt_edge[MAXM];           // 链式前向星的 next 指针
int edge_to[MAXM];            // edge_to[e]:第 e 条反向边的目标,即父亲怪兽编号
int ecnt;                     // 已加入的反向边条数

__int128 sump[MAXN];          // sump[i] = S_i + Σ dp[son]:普通攻击路线的当前代价
                              // ΣR_i * K_i 可达 1e6 * 5e14 = 5e20,超出 ll,必须用 __int128
ll dp[MAXN];                  // dp[i]:最优代价,恒 <= K_i <= 5e14,ll 装得下
__int128 pend[MAXN];          // pend[i]:dp[i] 已下降但还没推给父亲们的量
bool inq[MAXN];               // inq[i]:i 是否已在队列里,避免重复入队

// 快读:输入全是非负整数,最大 13MB,按块 fread + 手写解析
const int BUFSIZE = 1 << 16;
char ibuf[BUFSIZE];
int ipos = 0, ilen = 0;

// 取下一个字符,缓冲区空了就再读一块;返回 0 表示输入结束
char get_char() {
    if (ipos == ilen) {
        ilen = fread(ibuf, 1, BUFSIZE, stdin);
        ipos = 0;
        if (ilen <= 0) return 0;
    }
    return ibuf[ipos++];
}

// 读一个非负整数
ll read_int() {
    char c = get_char();
    while (c < '0' || c > '9') {
        if (c == 0) return 0;
        c = get_char();
    }
    ll x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = get_char();
    }
    return x;
}

// 加一条反向边 son -> parent:表示"son 号怪兽是 parent 号怪兽衍生出来的"
void add_edge(int son, int parent) {
    ecnt++;
    edge_to[ecnt] = parent;
    nxt_edge[ecnt] = head[son];
    head[son] = ecnt;
}

void solve() {
    N = read_int();
    st[1] = 1;
    for (int i = 1; i <= N; i++) {
        S[i] = read_int();
        K[i] = read_int();
        int r = read_int();
        st[i + 1] = st[i] + r;
        for (int e = st[i]; e < st[i + 1]; e++) {
            sons[e] = read_int();
        }
    }

    // 反向边 + 初值:dp 全取法术攻击的代价 K_i,于是 sump[i] = S_i + Σ K[son]
    for (int i = 1; i <= N; i++) {
        sump[i] = S[i];
        for (int e = st[i]; e < st[i + 1]; e++) {
            int son = sons[e];
            add_edge(son, i);
            sump[i] += K[son];
        }
    }

    queue<int> q;
    for (int i = 1; i <= N; i++) {
        dp[i] = K[i];
        inq[i] = false;
        pend[i] = 0;
    }
    // 谁一开始就"普通攻击更便宜",就先把它降下来、入队待传播
    for (int i = 1; i <= N; i++) {
        if (sump[i] < dp[i]) {
            pend[i] += dp[i] - sump[i];
            dp[i] = sump[i];
            inq[i] = true;
            q.push(i);
        }
    }

    // SPFA:出队时把这一轮攒下的下降量 d 推给所有父亲,父亲重新结算后可能继续下降
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        inq[u] = false;
        __int128 d = pend[u];
        pend[u] = 0;
        if (d == 0) continue;
        for (int e = head[u]; e != 0; e = nxt_edge[e]) {
            int p = edge_to[e];        // p 会产生 u,u 便宜了 p 的普通攻击也跟着便宜
            sump[p] -= d;
            if (sump[p] < dp[p]) {
                pend[p] += dp[p] - sump[p];
                dp[p] = sump[p];
                if (!inq[p]) {
                    inq[p] = true;
                    q.push(p);
                }
            }
        }
    }

    printf("%lld\n", dp[1]); // 只有 1 号怪兽入侵村庄,答案就是 dp[1]
}

int main() {
    solve();
    return 0;
}

复杂度

设 M=∑RiM = \sum R_i。按数据范围 2⩽N⩽2×1052 \leqslant N \leqslant 2 \times 10^5、M⩽106M \leqslant 10^6、 1⩽Si,Ki⩽5×10141 \leqslant S_i, K_i \leqslant 5 \times 10^{14}。建反向边与初值是 O(N+M)O(N + M)。 主循环是 SPFA:每个 fif_i 只下降、不上升,总下降次数 DD 决定总代价 O(N+M+D)O(N + M + D) (每次传播沿一条反向边走一步)。DD 在最坏情况下没有比 Bellman-Ford 更好的界,但本题每条普通攻击都是正代价、且 fif_i 被 KiK_i 死死卡住上界, 实际每个点只会被松弛常数次,10 个测试点里 C++ 最慢 0.0670.067 s、Python 最慢 0.450.45 s。 空间 O(N+M)O(N + M):反向边 MM 条、每个点三个数组,C++ 实测峰值 2626 MB。

总结

本题的形式是"决策依赖结果、结果又有环",属于最短路式的方程求解, 和 [USACO 2005 Dec] 的"牛的比赛"、SPFA 判负环同一族思路:写出方程 → 说明它是某个单调算子的最小不动点 → 用松弛法从初值往下推。三步里最容易漏掉的是中间那步:如果只看"有环"就断言不可解, 或者反过来直接按 DAG 拓扑序算,都会错。而"最小"两个字恰恰是环能被接受的原因—— fi⩽Kif_i \leqslant K_i 给了天然上界,使最小不动点存在且可由上往下迭代得到。

实现上的两个坑都来自同一个观察——只有会产生 uu 的怪兽才会因 fuf_u 变化而受影响: 一是必须建反向边(正向边帮不上忙),二是必须把下降量攒起来整批推(否则丢量)。 剩下的就是纯 SPFA 模板,连"判负环"都不用写:本题没有负代价边,队列一定排空。

顺带记一笔数据类型:ff 的值域被 KiK_i 卡在 5×10145 \times 10^{14},看上去 long long 绰绰有余, 但它是 ∑\sum 的部分和,而部分和的项数可以达到 10610^6,所以 sum 必须用 __int128。 "参与比较的中间量"和"最终答案"值域不同,是这类题常见的溢出来源。

数据来源说明:本题所在素材目录附带 data.py 生成脚本,说明随仓 data/ 的 10 个测试点是 自造数据(题面本身亦为网络重建),出题意图与原官方题目可能存在偏差;其中 1、2、3、5、9、10 六个结构确定的点可由闭式公式手算校验,本文解法与素材源 std.cpp 在这 10 个点上输出完全一致。

图示解析

样例的反向边与松弛顺序

样例的依赖关系(实线箭头:普通攻击 ii 会产生箭头指向的怪兽):

flowchart LR
    N1["1 号<br/>S=4 K=27"] -->|"2 只"| N2["2 号<br/>S=3 K=5"]
    N1 --> N3["3 号<br/>S=1 K=13"]
    N2 --> N2
    N3 --> N4["4 号<br/>S=5 K=6"]
    N3 --> N2

初始 f=(27,5,13,6)f = (27, 5, 13, 6),sum=(4+5+5+13, 3+5, 1+6+5, 5+6)=(27,8,12,11)\mathrm{sum} = (4+5+5+13,\ 3+5,\ 1+6+5,\ 5+6) = (27, 8, 12, 11)。 只有 33 号满足 sum<f\mathrm{sum} < f(12<1312 < 13,其余三点都是法术攻击更便宜),入队;33 号降到 1212 后把下降量 11 推给它的父亲 11 号 (sum1:27→26\mathrm{sum}_1: 27 \to 26),11 号随即降到 2626 并入队;11 号没有父亲,传播结束。 最终 f1=26f_1 = 26,与样例解释里 “普通攻击 11 号(44)→ 法术杀两只 22 号(1010)→ 普通攻击 33 号(11)→ 法术杀 22、44 号(1111)” 这条 4+5+5+1+5+6=264+5+5+1+5+6=26 的路线吻合。