把 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
形式化题目
有
- 普通攻击:消耗
体力把它"打死",但它死后会立刻产生 只新怪兽, 编号为给定的 (编号可重复,同一编号可以出现多次); - 法术攻击:消耗
体力把它彻底消灭,不产生任何新怪兽。
注意"普通攻击"并不减少怪兽总量(一只换成
正解
思路
先写出方程。 每只怪兽的处置彼此独立(
一只
样例可以验算:
难点在于它不是递推。 (1) 式右端依赖别的
为什么一定有解、解又是什么。 两条关键性质:
-
上界存在。
恒成立——法术攻击总是合法的,直接把它杀干净即可。 于是把所有 都取成 ,得到的是合法解的一个上界。 -
单调性。 (1) 式右端关于每个
单调不减。于是把它看成算子 , 从 出发反复做 ,序列单调不增且有下界, 必然收敛到最小不动点 ,而 就是要的答案: - 任何真实策略的代价都满足 (1) 式(策略要么一次法术杀掉,要么先普通攻击再分别处理衍生怪),
即每个合法策略的代价向量都是
的一个不动点(或前不动点),故 ; - 反过来,
是 (1) 式的最小解,按 里取到 的那一支构造策略即为合法策略, 代价恰好是 。
- 任何真实策略的代价都满足 (1) 式(策略要么一次法术杀掉,要么先普通攻击再分别处理衍生怪),
即每个合法策略的代价向量都是
这就是"最短路"视角:
朴素迭代慢在哪。 直接每轮全量扫一遍所有怪兽、把 (1) 式重算一次,
每轮代价
把影响面收窄。 维护
并为每个怪兽
若
下降了 ,则对每个父亲 : ; 若这时 ,就把 降到 ,并继续把 的下降量往外传。
初始状态与队列。 取
两个实现细节。
- 攒量而不是丢量。 同一只怪兽可能在出队前被连续降了多次。
给每个点配一个
pending[i],每次下降就累加进去,出队时一次性推给父亲; 否则后一次下降量会被前一次覆盖,答案偏大。同一个点还在队列里时不要重复入队(inq标记)。 - 中间量会爆
long long。,但 可能到 , 远超 long long的。C++ 里把 sum声明成__int128(只做加法和与f的比较,不参与输出),f保持long long。 不能简单地把sum截断饱和:下降后 sum会一路减回去,截断会丢掉这个减量。 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()/**
* 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;
}复杂度
设
总结
本题的形式是"决策依赖结果、结果又有环",属于最短路式的方程求解,
和 [USACO 2005 Dec] 的"牛的比赛"、SPFA 判负环同一族思路:写出方程 → 说明它是某个单调算子的最小不动点 →
用松弛法从初值往下推。三步里最容易漏掉的是中间那步:如果只看"有环"就断言不可解,
或者反过来直接按 DAG 拓扑序算,都会错。而"最小"两个字恰恰是环能被接受的原因——
实现上的两个坑都来自同一个观察——只有会产生
顺带记一笔数据类型:long long 绰绰有余,
但它是 sum 必须用 __int128。
"参与比较的中间量"和"最终答案"值域不同,是这类题常见的溢出来源。
数据来源说明:本题所在素材目录附带
data.py生成脚本,说明随仓data/的 10 个测试点是 自造数据(题面本身亦为网络重建),出题意图与原官方题目可能存在偏差;其中 1、2、3、5、9、10 六个结构确定的点可由闭式公式手算校验,本文解法与素材源std.cpp在这 10 个点上输出完全一致。
图示解析
样例的反向边与松弛顺序
样例的依赖关系(实线箭头:普通攻击
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
初始