问题分析

我们有：

• $n$ 个错误（$n \leq 20$）
• $m$ 个补丁，每个补丁有：
  • 适用条件：$B_1$（必须有的错误），$B_2$（必须没有的错误）
  • 效果：$F_1$（修复的错误），$F_2$（引入的错误）
  • 耗时 $t_i$

目标：从全错状态 $(11\ldots1)_2$ 到无错状态 $(00\ldots0)_2$ 的最短时间。

---

关键思路

状态表示

由于 $n \leq 20$，可以用二进制状态压缩：

• 状态 $S$ 是一个 $n$ 位二进制数
• 第 $k$ 位为 $1$ 表示存在第 $k$ 个错误，为 $0$ 表示已修复

状态转移

对于每个状态 $S$，尝试应用每个补丁 $i$：

检查补丁 $i$ 是否可用：

• $B_1(i)$ 中所有错误必须在 $S$ 中出现：(S & B1_mask) == B1_mask
• $B_2(i)$ 中所有错误必须在 $S$ 中不出现：(S & B2_mask) == 0

应用补丁 $i$ 后的新状态：

• 修复 $F_1(i)$ 中的错误：$S' = S \ \&\ \sim F1\_mask$
• 加入 $F_2(i)$ 中的错误：$S' = S' \ | \ F2\_mask$

边权：补丁 $i$ 的耗时 $t_i$

---

算法选择

这实际上是一个带权有向图最短路问题：

• 节点：所有 $2^n$ 个可能的状态
• 边：如果状态 $S$ 能通过补丁 $i$ 到达状态 $S'$，则有一条权值为 $t_i$ 的边

使用 Dijkstra 算法 求从全错状态到无错状态的最短路径。

---

样例验证

输入：

3 3
1 000 00-
1 00- 0-+  
2 0-- -++

$n=3$，初始状态 $111_2 = 7$，目标状态 $000_2 = 0$

补丁分析（错误编号从 0 开始，字符串从左到右对应错误 0,1,2）：

补丁1：耗时 1

• 条件：000 → $B1=0, B2=0$（无条件可用）
• 效果：00- → 修复错误2
• 转移：$S \rightarrow S \ \&\ \sim(001_2)$

补丁2：耗时 1

• 条件：00- → $B1=0, B2=(001_2)$（错误2必须不存在）
• 效果：0-+ → 修复错误1，引入错误2
• 转移：$(S \ \&\ \sim(010_2)) \ | \ (001_2)$

补丁3：耗时 2

• 条件：0-- → $B1=0, B2=(011_2)$（错误1,2必须不存在）
• 效果：-++ → 修复错误0，引入错误1,2
• 转移：$(S \ \&\ \sim(100_2)) \ | \ (011_2)$

最短路过程：

• $111 \xrightarrow{1} 110$（用补丁1修复错误2）
• $110 \xrightarrow{1} 101$（用补丁2修复错误1，引入错误2）
• $101 \xrightarrow{1} 100$（用补丁1修复错误2）
• $100 \xrightarrow{2} 011$（用补丁3修复错误0，引入错误1,2）
• $011 \xrightarrow{1} 010$（用补丁1修复错误2）
• $010 \xrightarrow{1} 001$（用补丁2修复错误1，引入错误2）
• $001 \xrightarrow{1} 000$（用补丁1修复错误2）

总耗时：$1+1+1+2+1+1+1 = 8$

---

算法步骤

1. 读入 $n, m$
2. 对每个补丁 $i$，预处理四个掩码：
   • $B1\_mask$：条件中必须存在的错误
   • $B2\_mask$：条件中必须不存在的错误
   • $F1\_mask$：修复的错误
   • $F2\_mask$：引入的错误
3. 初始化距离数组 $dist[0..2^n-1] = \infty$，$dist[2^n-1] = 0$（全错状态）
4. 使用优先队列运行 Dijkstra：
   • 对于当前状态 $S$，尝试每个补丁 $i$
   • 检查是否满足条件
   • 计算新状态 $S'$ 和新距离
   • 如果更优则更新
5. 输出 $dist[0]$，如果为 $\infty$ 则输出 $0$

---

复杂度分析

• 状态数：$2^n \leq 2^{20} = 1,048,576$
• 每个状态尝试 $m \leq 100$ 个补丁
• 总复杂度：$O(2^n \cdot m \cdot \log(2^n)) \approx 10^8$ 级别
• 在 $n=20$ 时稍大但可接受（实际很多状态不可达）

---

总结

这道题通过状态压缩表示错误集合，将补丁应用建模为状态转移，用最短路算法求解最小耗时，是状态空间搜索的经典例题。虽然归类在网络流 24 题中，但实际解法展示了不同算法在解决实际问题时的灵活性。