题意：首先给出n和m，表示有n个bug和m个补丁。一开始存在n个bug，用1表示一个bug存在0表示不存在，所以一开始就是n个1，我们的目的是要消除所有的bug，
所以目标状态就是n个0。对于每个补丁，会给出使用这个补丁的时间，另外会给出两个长度为n的字符串，第一个字符串表示这个补丁适用于什么情况下的bug，
第二个字符串表示使用完这个补丁后原来的bug会变成怎么样。先说第一个字符串，s[i]=’0’，表示第i个bug存在与否都无所谓；s[i]=’+’，
表示第i个bug一定要存在；s[i]=’-‘，表示第i个bug必须不存在；能不能使用这个补丁，就要看当前bug的状态是不是能不能全部满足第一个字符串，能的话就可以使用。
第二个字符串表示使用完后的情况，ss[i]=’0’，表示第i个bug保持不变，原来是1就1是0就0；ss[i]=’+’，表示第i个bug必须为1；ss[i]=’-‘，表示第i个bug必须为0。
最终题目要求解的就是消除所有的bug并且用时最短，输出最短时间，如果bug不可能被完全消除那么就输出。
析：我们首先对所有的状态进行压缩，然后对每个状态进行搜索，使用最短路，最后并对状态进行判断能不能进行打补丁，最后看
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <cmath>
#include <stack>
#include <sstream>
#define debug() puts("++++");
#define gcd(a, b) __gcd(a, b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define freopenr freopen("in.txt", "r", stdin)
#define freopenw freopen("out.txt", "w", stdout)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const double inf = 0x3f3f3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-5;
const int maxn = 1e6 + 10;
const int mod = 1e6;
const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, 1, 0, -1};
const char *de[] = {"0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111"};
int n, m;
const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
inline bool is_in(int r, int c){
return r >= 0 && r < n && c >= 0 && c < m;
}
struct Patch{
int bm, bp;
int am, ap;
int t;
};
Patch a[110];
char s1[25], s2[25];
int d[1<<20];
void print(int j){
for(int i = 0; i < n; ++i)
if(j & (1<<i)) putchar(‘1‘);
else putchar(‘0‘);
}
int dijstra(int s){
priority_queue<P, vector<P>, greater<P> > pq;
pq.push(P(0, s));
fill(d, d+(1<<20), INF);
d[s] = 0;
while(!pq.empty()){
P p = pq.top(); pq.pop();
if(p.second == 0) return p.first;
int v = p.second;
if(d[v] < p.first) continue;
for(int i = 0; i < m; ++i){
if(((p.second & a[i].bp) == a[i].bp) && ((p.second & a[i].bm) == 0)){
int u = (p.second | a[i].ap) & a[i].am;
if(d[u] > d[v] + a[i].t){
d[u] = d[v] + a[i].t;
pq.push(P(d[u], u));
}
}
}
}
return -1;
}
int main(){
int kase = 0;
while(scanf("%d %d", &n, &m) && m+n){
memset(a, 0, sizeof a);
for(int i = 0; i < m; ++i){
scanf("%d", &a[i].t);
scanf("%s", s1);
scanf("%s", s2);
a[i].am = (1<<n)-1;
for(int j = 0; j < n; ++j){
if(s1[j] == ‘+‘) a[i].bp |= (1<<j);
else if(s1[j] == ‘-‘) a[i].bm |= (1<<j);
if(s2[j] == ‘+‘) a[i].ap |= (1<<j);
else if(s2[j] == ‘-‘) a[i].am ^= (1<<j);
}
}
int ans = dijstra((1<<n)-1);
printf("Product %d\n", ++kase);
if(ans == -1) printf("Bugs cannot be fixed.");
else printf("Fastest sequence takes %d seconds.", ans);
puts("\n");
}
return 0;
}
是不是能完全打完所有的补丁，
由于是要时间是最少，所以我们可以用优先队列进行维护。
代码如下：
UVa 658 It's not a Bug, it's a Feature! (状态压缩+Dijstra)
原文：http://www.cnblogs.com/dwtfukgv/p/6415849.html