洛谷 P4042 分析（别看）

科技起源‍‍‍‍‍‍‍‍‍‍‍‍

2026-07-22 18:00:00

发布于：北京

8阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最小值

1.2 题目背景、允许、禁止与限制

背景：
有 $n$ 种怪兽，初始时有怪兽 $1$ ，求消灭这个怪兽最少需要多少体力
允许：
对于每个怪物 $i$ ，有两种攻击方式

物理攻击，需要耗费 $s_i$ 的体力，尽管当前怪物会被消灭，但是会分裂出 $r_i$ 个新的怪兽
魔法攻击，需要耗费 $k_i$ 的体力，不会有任何分裂，相当于彻底消灭

限制：

1.3 题目数据范围与猜测

$1 \le n \le 2\times10^5,1 \le \sum r_i \le 10^6 \longrightarrow O(\sum r~log~n)$

1.4 一句话概括题意

初始有一个怪兽，求通过不同攻击方式（消耗体力可能不同）将所有怪物击杀的最小体力耗费

2 题目破题推导

2.1 排除一些错误

不断模拟
怪兽的数量可以理解为是无限的，模拟就永无止境
构造有偏差的图
将每个点设置一条到 1 的路径权值为 k [i]，再设置连接到第 r [i] 个节点的权值为 s [i]，然后求 1~1 的最短路
这样也是不行的，因为比如分裂出来r_i个怪物，但是最短路只会走其中一条，是违背这题要求的

2.2 问题等价转化（抽象）

思考：任何一只怪兽，他的诞生时机和诞生方式都不影响彻底清除它的最小花费体力
因此，抽象出核心概念： $f(i)=$ 彻底清除第 $i$ 种怪物所需要的最小体力
那答案本质上就是 $f(1)$ ，因为开局有的怪兽就是 $1$

2.3 分情况讨论

每种怪兽 $i$ ，都只有两种可能

法术攻击：代价为 $k_i$ ，无新怪兽产生且原怪兽死亡
普通攻击：代价为 $s_i$ ，原怪兽死亡且产生一些新怪兽。总消耗可以理解成： $s_i+\sum f(所有新的怪物)$

$f(i) 即 min(k_i,s_i+\sum f(...))$

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

这题到这里大家可能觉得是普通 $\huge{dp}$
但是，因为假设攻击怪物 $a$ 会生出怪物 $b$ 且能更新最佳方案，那么 $f(a)$ 会随着 $f(b)$ 的变化而变化，并且 $f(b)$ 也会随着 $f(a)$ 的变化而变化
普通dp要求依赖构成DAG，这题是双向依赖关系，不能用朴素dp
因为我们每遇到一个新点，都有可能对上个节点及下个节点造成影响，因此这种不断松弛的操作，和 $\huge{最短路算法}$ 的想法一样。
但是，由于这题没有固定起点（因为所有点都会对其他点造成影响），因此起点不固定，考虑把所有起点都纳入最短路算法实现中

4 最终代码（禁止抄袭，仅用于参考）

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

inline int read(){
    int num = 0;
    int f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-'){
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        num = (num << 3) + (num << 1) + (ch ^ 48);
        ch = getchar();
    }
    return num * f;
}

int n;
const int N = 2e5 + 10;
int s[N], k[N], r[N];
vector<int> to[N], from[N];
void add(int u, int v){
    to[u].push_back(v);
    from[v].push_back(u);
}
bool vis[N];
int dis[N];
void spfa(){
    queue<int> q;
    for (int i = 1;i <= n;i++){
        q.push(i);
        vis[i] = true;
    }
    while(!q.empty()){
        int f = q.front();
        q.pop();
        vis[f] = false;
        int temp = s[f];
        for (int i = 0;i < to[f].size();i++){
            temp += dis[to[f][i]];
        }
        if (temp < dis[f]){
            dis[f] = temp;
            for (int i = 0;i < from[f].size();i++){
                if (!vis[from[f][i]]){
                    vis[from[f][i]] = true;
                    q.push(from[f][i]);
                }
            }
        }
    }
}

signed main(){

    n = read();
    for (int i = 1;i <= n;i++){
        s[i] = read(), k[i] = read(), r[i] = read();
        dis[i] = k[i];
        for (int j = 1;j <= r[i];j++){
            int x = read();
            add(i, x);
        }
    }
    spfa();
    cout << dis[1];
    
    return 0;
}