P10541 [THUPC 2024 决赛] 研发计划

看到近期若干家大模型创业公司获得高额融资，作为炼丹大师的你心痒难耐，决定入局，亲自下场搞产品。 经过一段时间的梳理，你发现当前共有 $m$ 种产品推出后将会大卖，其中第 $i$ 个产品推出之后预期获得 $g_i$ 的收益。这 $m$ 种产品涉及 $n$ 种技术：共有 $p$ 条技术-产品依赖关系 $(u,v)$ ，表示第 $u$ 个技术是第 $v$ 个产品的前置技术。对于每个产品，你必须获得它的全部前置技术之后才能推出。 对于第 $j$ 个技术，你可以选择花费 $f_j$ 的代价直接从其他公司购买获得，或者花费 $h_j$ 的代价通过研发获得。研发需要一定的条件：给出 $q$ 条技术-技术依赖关系 $(a,b)$ ，表示第 $a$ 个技术是第 $b$ 个技术的前置技术，那么必须在获得了技术 $j$ 的所有前置技术后才能通过研发获得技术 $j$ 。若某个技术没有前置技术，那么你可以直接通过研发获得。保证技术-技术依赖关系构成一个有向无环图，即不会发生循环依赖（自然不会有自环）。 一个方案的收益为推出的产品的收益总和减去获得的技术的代价总和。现在，作为一个商人，你希望研究一些技术、推出一些产品，最大化你获得的收益。为简单起见，你只要输出最大的收益值。

无

无

最优方案是依次研究技术 1，购买技术 3，研究技术 4，这时我们就能推出产品 1、4、5 了。此时收益为 $(2+8+8)-(1+6+3)=8$。 **来源与致谢** 来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。 数据、题面、标程、题解等请参阅 THUPC 官方仓库