题解 | #小红的魔法药剂#

解题思路

核心思想

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

对于第 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

示例验证

输入

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

处理过程

总成本：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];