小红收集魔法药剂 - 题解

题意精炼

有 种药剂，每种药剂有「红」「蓝」两种形态：

• 直接购买：第 种红色药剂单价为 。
• 调配合成：若已有「红色」的第 、第 种药剂，各消耗一瓶，可合成「蓝色」的第 种，合成本身不额外花费金币。

目标：使得最终对每个编号 至少拥有该药剂的任意一种形态（红或蓝），最小化总花费。

思路与结论

对每个编号 独立考虑一瓶“专属于 的药剂”的最小花费：

• 要么直接买红色 ：花费 。
• 要么用两瓶红色 、 合成蓝色 ：花费 。

于是对每个 的最优成本为： 将上述值对所有 直接求和即为答案。

关键点解释：题目允许购买任意数量的红色药剂；我们可以把“给第 种留的一瓶”独立出来计算成本（要么直接买一瓶红色 ，要么专门买一瓶红色 和一瓶红色 来合成一瓶蓝色 ）。这些“为不同 预留的一瓶”之间互不共享，因此直接求和即得到全局最优。

正确性说明

将每个 的那“一瓶”视为互不共享的资源：

• 若选择“红 ”，直接付 ；
• 若选择“蓝 ”，则为这瓶蓝 专门购入一瓶红 +一瓶红 ，付 。 两种方案中取较小者，彼此独立求和即可。任何试图“共用原料”的做法都会破坏“每个 至少一瓶”的独立性约束，不会比该独立最优更省。

复杂度

• 时间复杂度：
• 空间复杂度：（除输入存储外）

参考实现

#include <iostream>
using namespace std;
int a[202020];
int main() {
    int n,i;
    cin>>n;
    int res=0;
    for(i=1;i<=n;i++)cin>>a[i];
    for(i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        res+=min(a[i],a[x]+a[y]);
    }
    cout<<res;
}