做信奥题的人大概率都被题单名字骗过。洛谷“网络流24题”这个题单里混着不少根本和网络流八竿子打不着的题目P2761 软件补丁问题就是最典型的一个。我第一次看到这个题时以为要建模跑最大流或最小割结果翻开题解满屏都是状态压缩、SPFA、位运算当场意识到事情没那么简单。这道题的输入是 n 个 bug 和 m 个补丁每个补丁有安装条件和安装效果求把所有 bug 修好的最少时间。n 不超过 20这个数据范围几乎就是在明示用二进制位表示 bug 状态把所有状态当成图上的点然后跑最短路。这篇博客就围绕“状态压缩 最短路”这个核心思路展开把从读题、建模、预处理到最终 AC 的完整过程都过一遍适合正在刷状压题、准备信奥初赛复赛的选手参考也适合刚学完最短路算法想找实战题练手的同学。1. 先拆题软件补丁问题究竟在考什么1.1 题面里藏着的信号看到 n ≤ 20 就要想到状压题目的场景很直白程序有一堆 bug初始全部存在有 m 个补丁包每个补丁包有安装耗时安装前必须满足某些条件安装后会产生一系列修复和引入效果。问最少花多少时间能把所有 bug 修完。如果修不完输出 0。这个题干猛一看像是某种约束满足问题但注意看数据范围n 不超过 20m 不超过 100。20 这个数字在信奥题里非常有辨识度——2 的 20 次方是 1,048,576刚好是百万级别这个规模的数组或状态数完全可以在普通 OJ 上跑。反过来如果 n 是 100 甚至更大那就得考虑差分约束、网络流或者其他图论模型了。所以拿到题的第一步不是急着套模板而是先把数据范围这个最直接的信息抓出来20 位二进制就是这道题的解题入口。补丁的行为本质上是对 bug 集合做一次“条件判断 集合增减”这用二进制位运算描述非常自然。每个 bug 对应一位1 表示存在0 表示不存在所有 bug 的集合就对应一个整数。初始时所有 bug 都有状态就是全 1目标是一个 bug 都没有状态就是 0。每个补丁执行前要看当前状态满不满足条件执行后要把某些位变成 0、某些位变成 1。这不就是一张隐式的有向图吗节点是 2 的 n 次方个状态边是 m 种补丁操作每条边的权值是补丁耗时。1.2 把“打补丁”翻译成状态转移既然确定了状态压缩下一步就是把题面里的条件用位运算精确表达。对每个补丁 i需要维护四个掩码need[i]补丁要求必须存在的 bug 集合。只有当 (state need[i]) need[i] 时这些必需的 bug 才全部在位。forbid[i]补丁要求必须不存在的 bug 集合。只有当 (state forbid[i]) 0 时才满足“不能有这些 bug”的条件。fix[i]补丁安装后会修复的 bug 集合对应位要清零。add[i]补丁安装后会引入的 bug 集合对应位要置 1。转移公式是new_state (state ~fix[i]) | add[i]也就是说先把当前状态里所有会被修复的 bug 位清掉再把补丁新引入的 bug 位置上。这里需要注意的是如果某个 bug 同时出现在 fix 和 add 中从公式看是先清零后置 1最终该位是 1。在实际规则里一个补丁既修这个 bug 又引入同一个 bug 显然不合理但就算出现这种情况上面的公式也能给出确定性的结果逻辑上是自洽的。为什么不能直接贪心因为补丁之间不是独立的一个补丁可能为了修复某个 bug 而引入另一个 bug引入的 bug 又可能成为下一个补丁的前置条件。路径之间会形成环路直接每一步选耗时最短的补丁很容易绕进死胡同。最短路算法才是处理这种“带环路状态转移”的正解这也是本题和普通贪心题最大的区别。2. 预处理把补丁字符串翻译成四个位掩码2.1 四个掩码分别记录什么输入里每个补丁给出两个长度为 n 的字符串b1 表示安装条件b2 表示安装效果。字符只有三种’’、’-’、’0’。在 b1 中’’ 表示要求这个位置的 bug 存在’-’ 表示要求这个位置的 bug 不存在’0’ 表示无所谓在 b2 中’-’ 表示修复这个 bug’’ 表示引入这个 bug’0’ 表示无影响。所以预处理时对 b1 要生成两个掩码need 记录所有要求 bug 存在的位forbid 记录所有要求 bug 不存在的位。对 b2 也要生成两个掩码fix 记录所有要被修复清零的位add 记录所有要被引入置 1 的位。这四个掩码就是后续 SPFA 扩展状态时反复用到的“操作模板”。2.2 逐字符解析的常规写法预处理代码很短但却是最容易写错的一部分。我习惯写成下面这样#include bits/stdc.h using namespace std; const int MAXM 105; const int MAXN 20; const int INF 0x3f3f3f3f; int n, m; int cost[MAXM]; // 每个补丁的耗时 int need[MAXM], forbid[MAXM]; // b1 字符串产生的两个掩码 int fix[MAXM], add[MAXM]; // b2 字符串产生的两个掩码 int dist[1 MAXN]; // 状态码对应的最短耗时 int main() { ios::sync_with_stdio(false); cin.tie(0); cin n m; string s1, s2; for (int i 0; i m; i) { cin cost[i] s1 s2; for (int j 0; j n; j) { if (s1[j] ) need[i] | (1 j); else if (s1[j] -) forbid[i] | (1 j); if (s2[j] -) fix[i] | (1 j); else if (s2[j] ) add[i] | (1 j); } } // 后续最短路部分 int full (1 n) - 1; memset(dist, 0x3f, sizeof(dist)); queueint q; dist[full] 0; q.push(full); while (!q.empty()) { int u q.front(); q.pop(); for (int i 0; i m; i) { if ((u need[i]) ! need[i]) continue; if ((u forbid[i]) ! 0) continue; int v (u ~fix[i]) | add[i]; if (dist[v] dist[u] cost[i]) { dist[v] dist[u] cost[i]; q.push(v); } } } if (dist[0] INF) cout 0 \n; else cout dist[0] \n; return 0; }2.3 预处理里的三个细节第一个细节是1 j的 j 从 0 开始。bug 编号在题目描述里可能是 1 到 n但二进制位通常从第 0 位到第 n-1 位代码里直接用 j 从 0 遍历到 n-1 最省事。如果你想从 1 开始编号那1 (j-1)也能做但没必要给自己增加思考负担。第二个细节是 s1 和 s2 要用cin s1 s2读取。因为补丁行是“耗时 字符串 字符串”的结构字符串之间没有空格cin 天然会跳过空白字符所以这样读完全没有问题。千万不要用getline去读除非你愿意手动处理前面的数字和换行符那纯粹是给自己挖坑。第三个细节是关于数组大小。n 最大 20状态数最多 2^20也就是 1048576dist[1 MAXN]完全可以放下。如果用vectorint dist(1 n, INF)会更灵活n 很小的时候不浪费内存但静态数组在信奥代码里更直观两种写法都行。我用静态数组是因为 memset 初始化方便一个函数搞定。3. 核心实现让状态在图上跑最短路3.1 为什么是 SPFA 而不是 BFS有人可能会问状态图都建出来了用朴素 BFS 不也能求最短路径吗问题是 BFS 只适用于边权为 1 的情况而这道题每个补丁的耗时不一定相同边权可能是一个较大的整数普通 BFS 无法保证第一次扩展到某个状态时就是最短距离。解决办法有两种一是把耗时大于 1 的补丁拆成多条边权为 1 的边但这会显著扩大状态图规模几乎不可行二是直接上最短路算法SPFA、Dijkstra 都行。既然边权全是正数理论上堆优化的 Dijkstra 是最稳的。但很多题解选择 SPFA原因很实际SPFA 的队列操作常数小代码也短这道题的隐式状态图点数虽然多但每个点向外尝试的边数只有 m 条m 最多 100实际可达状态和松弛次数远没有到最坏情况。SPFA 最坏的 O(VE) 复杂度在这种特殊图上很难被卡到所以它在这题里是够用的。如果你对 SPFA 有心理阴影也可以用 Dijkstra后面我会单独聊两者的取舍。另一个关键认知是这张状态图是隐式图不需要真的把所有边提前建好。SPFA 每次从队列取出一个状态 u 时才临时循环 m 个补丁判断当前状态是否满足条件满足就算出一条出边。这种“边扩展边判断”的方式省掉了建图空间也正好匹配状压题“状态空间大、转移规则统一”的特点。3.2 完整代码主循环逐块拆解在我给出的完整代码里主循环分成三个部分。第一部分是取队首状态int u q.front(); q.pop();u 的二进制表示就是当前的 bug 集合。比如 n5 时状态 21 的二进制是 10101表示第 0、2、4 这三个 bug 还存在着。第二部分是尝试所有补丁for (int i 0; i m; i) { if ((u need[i]) ! need[i]) continue; if ((u forbid[i]) ! 0) continue; int v (u ~fix[i]) | add[i]; ... }(u need[i]) ! need[i]这个写法容易看错但它是标准的“判断集合包含关系”的方法。如果 u 中缺少 need[i] 里的任意一个 1那么按位与的结果就会少掉对应位就不再等于 need[i] 本身补丁不可用。(u forbid[i]) ! 0则是检查禁止集合是否与当前状态有交集只要有任意一个禁止的 bug 在位补丁同样不可用。第三部分是松弛并决定是否入队if (dist[v] dist[u] cost[i]) { dist[v] dist[u] cost[i]; q.push(v); }这里只在新距离严格小于旧距离时才更新并入队。如果 dist[v] 等于 dist[u] cost[i]说明已经有一条同样短的路径到达过 v再入队一次只会让后续重复扫描增加常数没有意义。这一行是 SPFA 能否高效工作的关键很多人在板子上抄的时候不重视等号问题结果队列里攒了一堆重复状态运气差就直接超时。3.3 边界情况修不完要输出 0题目里明确要求如果无法通过任何补丁组合把所有 bug 修完输出 0。因为初始状态 full 到目标状态 0 根本不在同一个连通分量里最短路计算结束后 dist[0] 仍然是 INF。所以我最后用三目运算符判断if (dist[0] INF) cout 0 \n; else cout dist[0] \n;这里不要习惯性输出 -1。很多最短路题无解输出 -1但这道题明确要求输出 0审题不清就会白白丢分。另外 INF 设成 0x3f3f3f3f 是因为两个 INF 相加不会溢出 int而且 memset 按字节填充非常方便这是 OI 里的一个通用技巧。另外提醒一点不能用反向最短路。有人会觉得既然从 full 到 0 不好搜那从 0 反着推回 full 行不行在多数无向图里反向跑没问题但这里的边是补丁操作方向性非常强补丁的“条件”和“效果”是完全不对称的两套掩码反向转移需要额外维护逆操作定义没有必要。老老实实从 full 出发正向跑即可。4. 细节打磨状态数、内存和算法选型4.1 状态规模到底有多大n20 时全状态数是 2^20也就是 1048576 个。dist 数组如果开成 int占 4MB 左右这在大部分 OJ 内存限制下毫无压力。队列里最多也就是把所有状态入队一次所以空间复杂度 O(2^n)。时间上SPFA 每弹出一个状态要扫描 m 个补丁每个补丁的判断和转移都是 O(1) 的位运算。理论上最坏是 O(2^n * m)也就是一亿次左右的位运算但 SPFA 不会对所有状态都反复松弛实际运行时远小于这个量级。这也是为什么这题敢把 n 放到 20位运算快状态数又刚好卡在百万级别整体能在合理时间内跑完。4.2 SPFA 和 Dijkstra 怎么取舍如果你用的是堆优化 Dijkstra核心做法是把队列换成优先队列按照 dist 从小到大取状态。代码改动其实不大priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; pq.push({0, full}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; for (int i 0; i m; i) { if ((u need[i]) ! need[i]) continue; if ((u forbid[i]) ! 0) continue; int v (u ~fix[i]) | add[i]; if (dist[v] d cost[i]) { dist[v] d cost[i]; pq.push({dist[v], v}); } } }理论上 Dijkstra 的复杂度更稳因为它不依赖图的性质。但在这道题里状态数是百万级堆操作会带来不小的常数而 SPFA 在随机状态图上通常表现很好。我的建议是能过题优先用自己熟悉的写法不要为了炫技临时换算法。如果你平时 Dijkstra 写得多、对 SPFA 心里没底那就直接用 Dijkstra如果你追求代码短、跑得快SPFA 完全没问题。两个版本我都实测过这道题都能过。4.3 从这题延伸出去隐式图搜索是个大考点P2761 的价值不只是让你会写一个状压最短路它揭示了信奥题里一类非常重要的题目形态搜索空间很大但状态转移规则简单统一不需要提前建图而是边搜索边生成后继状态。这类“隐式图”问题在八数码、01 背包变种、很多状态压缩 BFS 题里都会出现。它们的核心套路是先想清楚状态怎么编码再想清楚每一步怎么从当前状态生成邻居最后选择 BFS、最短路或 A* 等搜索方案套上去。这个思维链路一旦形成后续遇到类似的题会高效很多。5. 常见问题与避坑实录5.1 位运算优先级翻车现场C 里的优先级高于所以(u need[i]) need[i]外面的括号绝对不能省。如果写成u need[i] need[i]编译器会把表达式解析成u (need[i] need[i])也就是u 1。这意味着只有当状态的最低位是 1 时这个判断才可能为真补丁的条件判断完全错乱。我最早学位运算时就在这上面吃过亏当时调试了半天发现有的补丁莫名不能用有的又莫名能用逻辑怎么看都没问题最后才意识到是括号的锅。对策很简单所有位运算和比较运算符混合的表达式一律把位运算部分用括号包住不要依赖优先级记忆哪怕多写几层括号也无所谓可读性优先。5.2 ~fix[i] 的高位问题~fix[i]是对整个 int 取反如果 fix[i] 只有低 n 位有值取反后高位会变成 1。比如 n20fix[i] 的二进制只有低 20 位可能是 1取反后高 12 位就是 1。这时候执行u ~fix[i]因为 u 的高位本来全是 0按位与之后高位仍然是 0所以结果不受影响。从这个角度说(u ~fix[i]) | add[i]在代码里是安全的。但为了逻辑上更严谨、也为了让自己心里踏实可以用(u (~fix[i] full)) | add[i]先把取反后的高位重新切掉再和 u 做与运算。这两种写法结果一样第二种更直观第一种更简洁看个人习惯。5.3 队列入队条件里等号的差别SPFA 的入队条件写成dist[v] dist[u] cost[i]或者dist[v] dist[u] cost[i]看起来差不多实际上差别很大。用时即使没有产生更短距离只要找到一条等长路径就会再入队一次这会显著增加无谓的扩展次数。在状态数比较多的题里可能导致队列不断膨胀时间直接涨上去。我在调试别的题时遇到过这种问题改成严格大于之后运行时间立刻降了一个量级。5.4 审题上的小陷阱最后提两个和代码无关但容易翻车的点。第一个是输出 0 而不是 -1前面已经强调过。第二个是要理解“补丁可以重复安装”吗题目允许你多次使用同一个补丁吗实际上状态图上跑最短路时只要转移条件满足同一个补丁可以在不同状态反复使用SPFA 天然支持这种操作因为它是图上求最短路的通用算法不限制边被使用几次。如果你把补丁的使用次数当成限制条件反而会陷入复杂的建模误区。我个人在实际刷题时对这类“网络流 24 题”里混入的非网络流题目印象特别深。它逼我重新审视解题流程先看数据范围再想状态表示最后决定用哪种图搜索算法而不是看到题单名就条件反射去套模板。P2761 的核心就一句话n 到 20 的规模是状压的最强信号每个补丁是一次带权状态转移所有状态组成一张隐式图跑一遍最短路就能得到答案。把这种“从数据范围反推算法”的思路练熟比背一百道题的解都管用。