题目分析

我们有：

• $m$ 个实验，每个实验 $E_j$ 有收益 $p_j$
• $n$ 个仪器，每个仪器 $I_k$ 有费用 $c_k$
• 实验 $E_j$ 需要某些仪器 $R_j \subseteq I$
• 如果选择一个实验，则必须选择它需要的所有仪器
• 净收益 = 实验总收入 − 仪器总费用

目标：选择一部分实验（及所需仪器）使得净收益最大。

问题建模

这是一个依赖关系的选择问题：

• 实验有正权值（收益）
• 仪器有负权值（费用）
• 选择实验则必须选择它依赖的所有仪器

这正是最大权闭合子图的标准模型：

• 闭合子图：若选择一个点，则必须选择它的所有后继
• 权值：实验权值为 $p_j$，仪器权值为 $-c_k$
• 依赖关系：实验 → 所需仪器

最大权闭合子图转最小割

构造网络流图：

1. 源点 $s$ 向每个实验 $E_j$ 连边，容量 $p_j$
2. 每个仪器 $I_k$ 向汇点 $t$ 连边，容量 $c_k$
3. 每个实验 $E_j$ 向它需要的所有仪器 $I_k$ 连边，容量 $+\infty$

最大净收益 = 正权值和 − 最小割容量

其中：

• 正权值和 = $\sum_{j=1}^m p_j$
• 最小割 = 放弃的实验收益 + 选择的仪器费用

输出方案

在残量网络上从 $s$ 进行 BFS/DFS：

• 能到达的实验节点是被选择的实验
• 能到达的仪器节点是被选择的仪器

算法步骤

1. 读入 $m, n$
2. 读入每个实验的收益及所需仪器
3. 读入每个仪器的费用
4. 建图：
   • 节点：$s$（0）, 实验 $1..m$, 仪器 $m+1..m+n$, $t$（$m+n+1$）
   • $s$ → 实验 $j$：容量 $p_j$
   • 仪器 $k$ → $t$：容量 $c_k$
   • 实验 $j$ → 仪器 $k$：容量 $+\infty$（若需要）
5. 跑最大流（Dinic 或 Edmonds-Karp）
6. 计算净收益 = 总实验收益 − 最大流
7. 从 $s$ 在残量网络上 BFS 找出选择的实验和仪器
8. 输出方案

样例验证

输入：

2 3
10 1 2
25 2 3
5 6 7

建图：

• 实验1：收益10，需要仪器1,2
• 实验2：收益25，需要仪器2,3
• 仪器费用：5,6,7

网络流图：

• $s$ → 实验1：容量10
• $s$ → 实验2：容量25
• 仪器1 → $t$：容量5
• 仪器2 → $t$：容量6
• 仪器3 → $t$：容量7
• 实验1 → 仪器1,2：容量∞
• 实验2 → 仪器2,3：容量∞

最大流 = 18（计算得到） 净收益 = $(10+25) - 18 = 17$

选择方案：

• 实验：1,2
• 仪器：1,2,3

输出：

1 2
1 2 3
17

复杂度分析

• 节点数：$m+n+2 \leq 102$
• 边数：$O(mn)$
• Dinic 算法复杂度：$O(V^2E)$，在这里完全可行