C++ 魔法药剂收集最小花费问题

参考资料

问题描述

小红打算收集编号为 1∼n 的 n 种魔法药剂，其中每种药剂有两种形态：红色版本与蓝色版本。

获得药剂的方式如下：

  1. 直接购买：购买第 i 种红色版本药剂需要花费 a_i 金币
  2. 调配合成：若已拥有红色版本的第 b_i 种与第 c_i 种药剂，可调配得到蓝色版本的第 i 种药剂，调配本身不额外花费金币（仅需保证两种原料存在）

小红不关心颜色，只要求最终至少拥有 1∼n 每种药剂中的任意一种形态（红或蓝）。请计算她所需支付的最小总金币数。

输入格式

  • 第一行：整数 n (1 ≤ n ≤ 10^5)，表示药剂种类数量
  • 第二行：n 个整数 a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^4)，表示购买第 i 种红色药剂的价格
  • 接下来 n 行：第 i 行输入两个整数 b_i, c_i (1 ≤ b_i, c_i ≤ n)，表示合成蓝色版本第 i 种药剂所需的两种红色药剂的编号

输出格式

输出一个整数，表示获得 n 种不同药剂所需支付的最小金币数。

示例

输入：

5
2 4 10 1 3
2 3
4 5
1 2
2 5
1 4

输出：

16

说明：

一种最优方案：

  • 直接购买第 1,2,4,5 种红色药剂，花费 2+4+1+3=10
  • 利用红色的 1,2 调配得到第 3 种蓝色药剂，花费 2+4=6
  • 最终花费 10+6=16

解题思路

核心思想

这道题的关键是理解：对于每种药剂，我们需要独立决定是获得红色版本还是蓝色版本。

对于第 i 种药剂，有两种选择：

  1. 选择红色版本：成本为 cost[i]
  2. 选择蓝色版本：成本为 cost[b_i] + cost[c_i]

这里需要注意的是：合成蓝色药剂的成本是购买两种红色原料的成本之和，即使我们为了其他药剂已经”购买”过这些原料，仍然需要重新计算成本。

贪心策略

对于每种药剂 i，我们选择成本更低的方案：

min_cost[i] = min(cost[i], cost[b_i] + cost[c_i])

最终答案为所有药剂的最小成本之和。

为什么贪心是正确的？

这道题可以看作是一个独立选择问题：

  • 每种药剂的选择不会影响其他药剂的选择
  • 每种药剂的成本计算是独立的
  • 因此对每种药剂选择局部最优解，就能得到全局最优解

代码实现

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

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

    int n;  // 药剂种类数量
    cin >> n;

    // 存储每种红色药剂的购买价格
    vector<int> red_cost(n);
    for (int i = 0; i < n; ++i) {
        cin >> red_cost[i];
    }

    ll total_cost = 0;  // 最小总花费

    // 对每种药剂，计算获得它的最小成本
    for (int i = 0; i < n; ++i) {
        // 读取合成配方
        pair<int, int> recipe; // 合成第 i 种蓝色药剂需要的两种红色药剂编号
        cin >> recipe.first >> recipe.second;

        // 计算两种获得方式的成本
        int cost_buy_red = red_cost[i]; // 直接购买红色
        int cost_make_blue = red_cost[recipe.first - 1] + red_cost[recipe.second - 1];  // 合成蓝色

        // 选择成本较低的方案
        total_cost += min(cost_buy_red, cost_make_blue);
    }

    //输出
    cout << total_cost << '\n';

    return 0;
}

代码解析

关键步骤

  1. 读取输入

    int n;
cin >> n;
vector<int> red_cost(n);
for (int i = 0; i < n; ++i) {
    cin >> red_cost[i];
}

  2. 对每种药剂做决策

    for (int i = 0; i < n; ++i) {
    // 读取配方
    pair<int, int> recipe;
    cin >> recipe.first >> recipe.second;
    
    // 计算两种方案的成本
    int cost_buy_red = red_cost[i];
    int cost_make_blue = red_cost[recipe.first - 1] + red_cost[recipe.second - 1];
    
    // 选择更优方案
    total_cost += min(cost_buy_red, cost_make_blue);
}

  3. 注意索引转换

    • 题目中药剂编号从 1 开始
    • 数组索引从 0 开始
    • 因此需要 recipe.first - 1 和 recipe.second - 1

复杂度分析

  • 时间复杂度：O(n)

    • 读取 n 个价格：O(n)
    • 处理 n 种药剂，每种 O(1)：O(n)
    • 总计：O(n)

  • 空间复杂度：O(n)

    • 存储 n 个价格的数组：O(n)

示例验证

输入

5
2 4 10 1 3
2 3
4 5
1 2
2 5
1 4

处理过程

药剂编号 红色成本 配方 蓝色成本 选择 成本
1 2 (2,3) 4+10=14 红色 2
2 4 (4,5) 1+3=4 两者均可 4
3 10 (1,2) 2+4=6 蓝色 6
4 1 (2,5) 4+3=7 红色 1
5 3 (1,4) 2+1=3 两者均可 3

总成本：2 + 4 + 6 + 1 + 3 = 16 ✓

代码运行

输入：
5
2 4 10 1 3
2 3
4 5
1 2
2 5
1 4

输出：
16

易错点

错误理解 1：原料复用

❌ 错误想法：购买一些红色药剂，然后用它们可以免费合成多个蓝色药剂。

✅ 正确理解：每种药剂的成本是独立计算的，不存在”原料复用”的概念。

错误理解 2：全局优化

❌ 错误想法：需要枚举所有可能的购买方案，找到全局最优解。

✅ 正确理解：这是一个独立决策问题，每种药剂选择局部最优即可。

索引转换

// ❌ 错误：直接使用编号
int cost_make_blue = red_cost[recipe.first] + red_cost[recipe.second];

// ✅ 正确：编号减1转为索引
int cost_make_blue = red_cost[recipe.first - 1] + red_cost[recipe.second - 1];

扩展思考

变体 1：限制购买数量

如果题目要求最多只能购买 k 种红色药剂，该如何解决？

思路：这就变成了一个更复杂的优化问题，需要考虑依赖关系，可能需要用到图论或动态规划。

变体 2：合成也需要花费

如果合成蓝色药剂本身也需要花费 cost_mix[i]，该如何修改？

修改：

int cost_make_blue = red_cost[recipe.first - 1] + red_cost[recipe.second - 1] + cost_mix[i];

变体 3：考虑依赖关系

如果合成配方可能形成依赖环（例如：蓝1需要红2，蓝2需要红1），该如何处理？

思路：需要检测环并做特殊处理，保证至少有一个被购买为红色版本。

总结

这道题的核心是：

  1. 正确理解题意：每种药剂的成本是独立计算的
  2. 贪心策略：对每种药剂选择成本更低的方案
  3. 注意细节：索引转换（编号从1开始，数组从0开始）

代码简洁高效，时间复杂度为 O(n)，适合处理题目给定的数据规模（n ≤ 10^5）。