软件补丁问题
不知道为什么放在网络流24题里面，我感觉是状压。
一个软件中有(n)个错误，共(m)个补丁程序。每一个补丁程序都有其特定的适用环境。对于每一个补丁(i)都有(2)个与之相应的错误集合(B1[i])和，(B2[i])使得仅当软件包含(B1[i])中的所有错误，而不包含(B2[i])中的任何错误时，才可以使用补丁(i)。补丁(i)将修复软件中的某些错误(F1[i])，而同时加入另一些错误(F2[i])。每个补丁都耗费一定的时间。
试设计一个算法，利用(m)个补丁程序将原软件修复成一个没有错误的软件，并使修复后的软件耗时最少。对于给定的(n)个错误和(m)个补丁程序，找到总耗时最少的软件修复方案。
输入格式：
第 1 行有 2 个正整数(n)和(m)，(n)表示错误总数，(m)表示补丁总数，(1leq nleq20), (1leq mleq 100)。
接下来(m)行给出了(m)个补丁的信息。每行包括一个正整数，表示运行补丁程序(i)所需时间，以及(2)个长度为(n)的字符串，中间用一个空格符隔开。
第(1)个字符串中，如果第(k)个字符(bk)为“(+)”，则表示第(k)个错误属于(B1[i])，若为“(-)”，则表示第(k)个错误属于(B21[i])，若为“(0)”，则第(k)个错误既不属于(B1[i])也不属于(B2[i])，即软件中是否包含第(k)个错误并不影响补丁(i)的可用性。
第(2)个字符串中，如果第(k)个字符(bk)为“(-)”，则表示第(k)个错误属于(F1[i])，若为“(+)”，则表示第(k)个错误属于(F2[i])，若为“(0)”，则第(k)个错误既不属于(F1[i])也不属于(F2[i])，即软件中是否包含第(k)个错误不会因使用补丁(i)而改变。
输出格式：
程序运行结束时，将总耗时数输出。如果问题无解，则输出(0)。
(Solution)
因为数据范围很小，所以我一开始想到的是状压。
状压的状态就是软件错误的状态。总共是(2^{20})种，开一个数组(dis)表示到达某种状态的最短时间，那么最后的答案就是(dis[0])（我以"(1)"为“有错误”）
首先，读入。
将(B1)和(B2)分开存。由题面可知，如果(B1|x==x)，这说明(x)中包含(B1)，若(B2)&(x==0)，则说明(B2)和(x)没有交集。这样就可以判断某个修补程序是否可用。
而(F)的读入方法类似。两个分开存。
int x = now ^ (now & f1[i]);
x |= f2[i];
(now)是当前状态，(x)是使用修补程序后的状态。这个式子应该不难推。
剩下的就是跑最短路了。相当于在状态之间连边，“距离”为最小时间。
(code)
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
long long read(){
long long x = 0; int f = 0; char c = getchar();
while(c < '0' || c > '9') f |= c == '-', c = getchar();
while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return f? -x:x;
}
int n, m, S, t[105], b1[105], b2[105], f1[105], f2[105], dis[1<<21];
bool vis[1<<21];
bool judge(int x, int u){//判断程序是否可用
if((b1[u] | x) != x) return false;
if(b2[u] & x) return false;
return true;
}
void spfa(){
memset(dis, 0x3f3f3f3f, sizeof dis);
queue<int> q;
q.push(S), dis[S]=0;
while(!q.empty()){
int now = q.front(); q.pop();
for(int i = 1; i <= m; ++i){
if(!judge(now, i)) continue;
int x = now ^ (now & f1[i]);
x |= f2[i];//计算新的状态
if(dis[x] > dis[now] + t[i]){
dis[x] = dis[now] + t[i];
if(!vis[x]) q.push(x), vis[x] = 1;
}
}
vis[now] = 0;
}
}
string s;
int main(){
n = read(), m = read();
S = 1 << n, --S;
for(int i = 1; i <= m; ++i){
t[i] = read(), cin >> s;//读入
for(int j = 0; j < n; ++j)
if(s[j] == '+') b1[i] += 1 << j;
else if(s[j] == '-') b2[i] += 1 << j;
cin >> s;
for(int j = 0; j < n; ++j)
if(s[j] == '-') f1[i] += 1 << j;
else if(s[j] == '+') f2[i] += 1 << j;
}
spfa();
if(dis[0] == 0x3f3f3f3f) puts("0");//特判
else printf("%d", dis[0]);
return 0;
}