题目分析

JYY 需要杀死入侵的怪兽，有两种攻击方式：

• 普通攻击：消耗 $S_i$ 体力，怪兽死亡后产生 $R_i$ 个新怪兽
• 法术攻击：消耗 $K_i$ 体力，直接彻底杀死怪兽

初始只有 1 号怪兽，需要找到杀死所有怪兽的最小体力消耗。

解题思路

核心思想

将问题建模为有向图，使用类拓扑排序和动态规划相结合的方法：

1. 图建模：怪兽之间的转化关系构成有向边
2. 动态规划：f[i] 表示杀死一个 i 号怪兽的最小花费
3. 贪心处理：使用优先队列总是处理当前最优的怪兽

关键观察

• 对于每个怪兽，最优策略是 min(法术攻击, 普通攻击+后续总花费)
• 当某个怪兽的所有转化目标的最小花费确定后，才能确定该怪兽的最小花费

算法步骤

1. 构建图结构：记录怪兽之间的转化关系
2. 初始化优先队列：将所有怪兽的法术攻击花费作为初始值
3. 拓扑处理：按花费从小到大处理，更新依赖关系
4. 输出结果：当处理到 1 号怪兽时输出答案

完整代码

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

const int N = 2e5 + 7;
const int inf = 2e9 + 7;

// f[i]: 杀死一个i号怪兽的最小体力花费
// d[i]: 对i号怪兽使用普通攻击后，产生的所有后续怪兽的总花费
ll f[N], d[N];

// deg[i]: i号怪兽的入度（依赖的其他怪兽数量）
// vis[i]: 标记是否已处理
int deg[N];
bool vis[N];

// G[a]: 存储从怪兽a能转化到的怪兽列表
vector<int> G[N];

void solve() {
    // 使用最大堆存储负值，实现最小堆效果
    priority_queue<pair<ll, int>> q;
    int n;
    cin >> n;
    
    // 读入数据并构建图
    for (int i = 1; i <= n; ++i) {
        int k;
        // 读入：普通攻击花费，法术攻击花费，产生怪兽数量
        cin >> d[i] >> f[i] >> k;
        
        // 读入产生的怪兽编号
        while (k--) {
            int a;
            cin >> a;
            // 添加边：a -> i，表示杀死a会产生i
            G[a].emplace_back(i);
            // i的入度增加，表示i依赖于a
            deg[i]++;
        }
        
        // 初始将每个怪兽的法术攻击花费加入优先队列
        q.push({-f[i], i});
    }
    
    // 主处理循环
    while (!q.empty()) {
        // 取出当前花费最小的怪兽
        int u = q.top().second;
        q.pop();
        
        // 如果已经处理过，跳过
        if (vis[u])
            continue;
        
        // 如果处理到1号怪兽，输出答案并返回
        if (u == 1) {
            cout << f[1] << '\n';
            return;
        }
        
        // 标记为已处理
        vis[u] = 1;
        
        // 更新所有依赖于当前怪兽u的怪兽v
        for (auto v : G[u]) {
            // 剪枝：如果v已经有更优解，跳过
            if (f[v] <= f[u])
                continue;
            
            // 累计普通攻击的后续花费
            d[v] += f[u];
            // 减少依赖计数
            deg[v]--;
            
            // 如果v的所有依赖都已处理完成
            if (!deg[v]) {
                // 更新v的最小花费：法术攻击 vs 普通攻击+后续
                f[v] = min(f[v], d[v]);
                // 将更新后的花费加入优先队列
                q.push({-f[v], v});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int t = 1;
    // 可以处理多组测试数据，但题目通常只有一组
    while (t--)
        solve();
    
    return 0;
}

代码说明

关键数据结构

• f[i]：动态规划数组，存储杀死怪兽 i 的最小花费
• d[i]：累计数组，存储对怪兽 i 使用普通攻击后的总后续花费
• deg[i]：入度数组，记录怪兽 i 还依赖多少个其他怪兽
• G[a]：邻接表，记录从怪兽 a 能转化到哪些怪兽

算法流程详解

1. 初始化阶段：

   for (int i = 1; i <= n; ++i) {
       cin >> d[i] >> f[i] >> k;
       // 构建图关系
       // 初始将法术攻击花费加入队列
   }
   

2. 处理阶段：

   • 每次从队列中取出当前花费最小的怪兽 u
   • 如果 u 是目标怪兽（1号），输出答案
   • 否则更新所有依赖于 u 的怪兽 v：
     • 累计普通攻击后续花费：d[v] += f[u]
     • 减少依赖计数：deg[v]--
     • 如果依赖为 0，更新最小花费并加入队列

正确性保证

• 最优子结构：每个怪兽的最小花费依赖于其转化目标的最小花费
• 贪心选择：总是优先处理当前花费最小的怪兽，确保正确传播花费
• 依赖管理：通过入度机制确保所有依赖都被正确处理

复杂度分析

• 时间复杂度：$O((N + \sum R_i) \log N)$
  • 每个节点入队一次：$O(N \log N)$
  • 每条边被遍历一次：$O(\sum R_i)$
• 空间复杂度：$O(N + \sum R_i)$
  • 存储图结构：$O(N + \sum R_i)$
  • 数组存储：$O(N)$