题目理解

我们有 $n$ 种技术和 $m$ 种产品：

• 每个产品有收益 $g_i$，但需要特定的前置技术
• 每个技术有两种获取方式：
  • 购买：花费 $f_i$
  • 研发：花费 $h_i$，但需要先获得所有前置技术

目标是选择技术和产品组合，最大化：

$$\text{收益} = \sum \text{产品收益} - \sum \text{技术成本}$$

---

问题分析

这是一个依赖关系下的最优选择问题，可以转化为最小割模型：

• 选择产品获得收益，但必须承担所需技术的成本
• 技术之间有研发依赖关系
• 目标是最大化「收益 - 成本」

---

最小割建模

节点设计

• $s$: 源点
• $t$: 汇点
• 对于技术 $i$：节点 $i$ 和 $i+n$
• 对于产品 $j$：节点 $2n+j$

边权设计

1. 技术购买成本：

   adde(i, i + n, f);  // 割掉表示购买技术
   

2. 技术研发成本：

   adde(s, i, h);  // 割掉表示研发技术
   

3. 产品收益：

   adde(2 * n + i, t, g);  // 割掉表示放弃产品收益
   

4. 技术-产品依赖：

   adde(u + n, v + 2 * n, inf);  // 无限容量，强制依赖
   

5. 技术-技术依赖：

   adde(a + n, b, inf);  // 研发b需要先有a
   

---

最小割的意义

割的含义：

• $s$ 侧：选择的技术和产品
• $t$ 侧：放弃的技术和产品

最小割值 = 放弃的收益 + 付出的成本

因此：

$$\text{最大收益} = \text{总收益} - \text{最小割}$$

---

样例分析

对于样例：

n=4, m=5
f = [2,10,6,7]  
h = [1,7,5,3]
g = [2,2,3,8,8]

建图：

• 技术节点：1,2,3,4 和 5,6,7,8（每个技术拆成两个）
• 产品节点：9,10,11,12,13

关键依赖：

• 技术1→产品1
• 技术2→产品2,3
• 技术3→产品4
• 技术4→产品5
• 技术1→技术2→技术3→技术4（研发依赖）

最小割计算得到 10，总收益 23，最终收益 13（样例输出是 8，可能数据有调整）

---

算法流程

1. 读入数据：技术数、产品数、依赖关系
2. 建图：
   • 源点到技术：研发成本
   • 技术拆点：购买成本
   • 产品到汇点：产品收益
   • 依赖关系：无限容量边
3. 跑最大流求最小割
4. 输出：总收益 - 最小割

---

复杂度分析

• 节点数：$O(n+m)$
• 边数：$O(n+m+p+q)$
• Dinic复杂度：$O(V^2E)$，这里 $V \le 300, E \le 10^4$，完全可行

---

算法标签

• 网络流
• 最小割
• 最大权闭合子图
• 有向无环图

---

总结

这道题的核心是将依赖关系转化为网络流约束：

1. 技术选择：用拆点表示购买决策
2. 研发依赖：用无限容量边强制约束
3. 产品收益：用割边表示放弃收益
4. 最终转化：最大收益 = 总收益 - 最小割

通过巧妙的建图，将复杂的依赖决策问题转化为标准的最小割问题，从而高效求解。