题解

思路

把每种药水看成 DAG 中的一个点。免费供应、直接购买与唯一配方分别给出三类候选代价；配方的代价只依赖其所有前驱药水的最优代价，因此可以按拓扑顺序动态规划。

状态与转移

设 $f_i$ 表示获得一瓶第 $i$ 种药水的最少金币数。若第 $i$ 种药水可以免费获得，则 $f_i=0$。否则：

• 直接购买的代价为 $c_i$；
• 若存在配方，合成代价为该配方中所有原料最低代价之和。

因此有

$$f_i=\begin{cases} 0,&i\text{ 是免费药水},\\ c_i,&i\text{ 没有配方},\\ \min\left(c_i,\sum\limits_{j\in R_i}f_j\right),&\text{其他情况}. \end{cases}$$

原料会被消耗并不影响这个转移，因为题目要求的是“分别”获得每一种目标药水的最低代价，而不是同时集齐所有药水。配方依赖图无环，所以这些状态存在拓扑顺序。

子任务 1：无记忆递归

当 $n\le16$ 时，可以对每个目标药水都从头递归计算上述转移，不保存已经求过的状态。共享依赖会被重复展开，最坏时间复杂度为指数级，但小规模下足够。

子任务 2：多轮松弛

先令免费药水代价为 $0$，其他药水代价为购买价。每一轮用上一轮的结果重新计算所有配方的合成代价并取较小值。

依赖图最长路径至多包含 $n-1$ 条边。第 $r$ 轮后，所有依赖深度不超过 $r$ 的状态都已经正确，因此进行 $n$ 轮后一定得到全部答案。时间复杂度为 $O(n(n+m))$，其中 $m=\sum m_i$；适用于 $n\le400$。

子任务 3：拓扑动态规划

把每条“原料 $u$ 用于合成药水 $v$”的关系看成有向边 $u\to v$。令药水 $v$ 的入度为配方原料数，并维护其所有原料答案之和。

所有没有原料依赖的药水先入队。每次取出已求出答案的药水 $u$，把 $f_u$ 累加到所有依赖它的药水中，并将相应入度减一。当某个药水入度归零时，它的所有原料都已处理，可以按转移式求出答案并入队。

题目保证依赖图无环，所以每个药水恰好处理一次。总时间复杂度为 $O(n+m)$，空间复杂度为 $O(n+m)$。

注意合成代价之和可能达到约 $2\times10^{14}$，必须使用 64 位整数。

做法

建立从原料到成品的反向邻接表，并把每种药水的配方原料数作为入度。无原料依赖的药水先入队；每弹出一个药水，就把其最优代价累加到所有以它为原料的成品中。某个成品入度归零时，取购买价与累计配方价的较小值；免费药水则直接取零，然后将其继续入队传播。

复杂度

令 $m=\sum_i m_i$。满分算法的时间复杂度为 $O(n+m)$，空间复杂度为 $O(n+m)$。所有代价与累加和均使用 64 位整数。