

$12.$软件补丁问题

题目

T 公司发现其研制的一个软件中有 $n$ 个错误，随即为该软件发放了一批共 $m$ 个补丁程序。每一个补丁程序都有其特定的适用环境，某个补丁只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用。一个补丁在排除某些错误的同时，往往会加入另一些错误。

换句话说，对于每一个补丁 i，都有 2 个与之相应的错误集合 $B1[i]$和 $B2[i]$，使得仅当软件包含 $B1[i]$ 中的所有错误，而不包含 $B2[i ]$中的任何错误时，才可以使用补丁 $i$。补丁 $i$ 将修复软件中的某些错误 $F1[i]$，而同时加入另一些错误 $F2[i]$。另外，每个补丁都耗费一定的时间。

试设计一个算法，利用 T 公司提供的 $m$ 个补丁程序将原软件修复成一个没有错误的软件，并使修复后的软件耗时最少。对于给定的 $n$ 个错误和 $m$ 个补丁程序，找到总耗时最少的软件修复方案。

题解

这题感觉不用网络流啊。 直接用状压就行了。 都不用怎么讲。 按照题目把这些集合用二进制状压，1表示满足，0表示不满足。 然后用状态暴力spfa转移。