UVa 658 It's not a Bug, it's a Feature!

  It's not a Bug, it's a Feature! 

It is a curious fact that consumers buying a new software product generally do not expect the software to be bug-free. Can you imagine buying a car whose steering wheel only turns to the right? Or a CD-player that plays only CDs with country music on them? Probably not. But for software systems it seems to be acceptable if they do not perform as they should do. In fact, many software companies have adopted the habit of sending out patches to fix bugs every few weeks after a new product is released (and even charging money for the patches).

Tinyware Inc. is one of those companies. After releasing a new word processing software this summer, they have been producing patches ever since. Only this weekend they have realized a big problem with the patches they released. While all patches fix some bugs, they often rely on other bugs to be present to be installed. This happens because to fix one bug, the patches exploit the special behavior of the program due to another bug.

More formally, the situation looks like this. Tinyware has found a total of n bugs $B= {b_1, b_2, dots, b_n}$ in their software. And they have released m patches $p_1, p_2, dots, p_m$. To apply patch pi to the software, the bugs$B^+_i subseteq B$ have to be present in the software, and the bugs $B^-_i subseteq B$ must be absent (of course $B^+_i cap B^-_i = emptyset$holds). The patch then fixes the bugs $F^-_i subseteq B$ (if they have been present) and introduces the new bugs$F^+_i subseteq B$ (where, again, $F^-_i cap B^-_i = emptyset$).

Tinyware's problem is a simple one. Given the original version of their software, which contains all the bugs in B, it is possible to apply a sequence of patches to the software which results in a bug- free version of the software? And if so, assuming that every patch takes a certain time to apply, how long does the fastest sequence take?

Input 

The input contains several product descriptions. Each description starts with a line containing two integersn and m, the number of bugs and patches, respectively. These values satisfy $1 le n le 20$ and $1 le m le 100$. This is followed by m lines describing the m patches in order. Each line contains an integer, the time in seconds it takes to apply the patch, and two strings of n characters each.

The first of these strings describes the bugs that have to be present or absent before the patch can be applied. The i-th position of that string is a ``+'' if bug bi has to be present, a ``-'' if bug bi has to be absent, and a `` 0'' if it doesn't matter whether the bug is present or not.

The second string describes which bugs are fixed and introduced by the patch. The i-th position of that string is a ``+'' if bug bi is introduced by the patch, a ``-'' if bug bi is removed by the patch (if it was present), and a ``0'' if bug bi is not affected by the patch (if it was present before, it still is, if it wasn't, is still isn't).

The input is terminated by a description starting with n = m = 0. This test case should not be processed.

Output 

For each product description first output the number of the product. Then output whether there is a sequence of patches that removes all bugs from a product that has all n bugs. Note that in such a sequence a patch may be used multiple times. If there is such a sequence, output the time taken by the fastest sequence in the format shown in the sample output. If there is no such sequence, output ``Bugs cannot be fixed.''.

Print a blank line after each test case.

Sample Input 

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

Sample Output 

Product 1
Fastest sequence takes 8 seconds.

Product 2
Bugs cannot be fixed.
Miguel Revilla 
2000-05-22

题目的背景是说，给出一个有若干Bug的程序和一些补丁包，其中每个补丁包都在特定的条件下才可以使用，它可以修复一些存在的Bug同时可能产生一些新Bug。每个补丁包都有不同的运行时间，求最少用多少时间可以修复好所有Bug

首先Bug最多只存在20个，可以考虑用二进制进行状态压缩，每一位上等于1表示存在这个Bug，等于0表示不存在。之后我们就会发现，打补丁的方法相当于在各种状态之间建立了一些权值不同的边，这样题目就转化为了求状态为(1<<n)-1的点到状态为0的点之间的最短路径的长度

其中补丁包使用条件的判断以及建图是难点，这里我都用了位运算

　　先说条件判断：每个补丁包给出的第一个字符串是它的使用条件，可以做如下处理，将字符串中所有的+和-置为1，所有的0仍保持为0，得到了第一个二进制数，记为test。再将所有的+置为1，所有的-和0置为0，得到了第二个二进制数记为ans。则对于每个状态x，如果x&test==ans，则它可以使用这个补本包，反之不可以。这里的原理在于，字符串中的0表示程序中存不存在这个Bug均可，那么我们不论这位本来是1还是0，它与0进行与运算之后都为0；字符串中的+表示必须存在这个Bug，那么只有这一位是1，与1进行与运算之后的结果才是1，如果运算之后的结果是0，则说明不符合条件；字符串中的-表示必须不存在这个Bug，那个只有这一位是0，与1进行与运算之后的结果才是0，如果运算之后的结果是1，则说明不符合条件。由此我们知道了test和ans这两个数是怎么得到的。

　　至于建图，就是把一个状态和它通过某个补丁包得到的另一个状态连接起来存入邻接表中。另一个状态的求法就是把当前状态的二进制数中，修好的Bug位改为0，而新出现的Bug位改为1。将一个二进制数中的某一位置1的方法就是再构造另一个二进制数，只有要修改的位为1，其它位为0，然后将新构造的数与待修改的数进行或运算。将一个二进制数中的某一位置0的方法就是再构造另一个二进制数，只有要修改的位为0，其它位为1，然后将新构造的数与待修改的数进行与运算。

　　接下来求最短路径，SPFA即可

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<queue>
  5 #define INF 0x7fffffffffffffff
  6 
  7 using namespace std;
  8 
  9 typedef struct
 10 {
 11     int time;
 12     int test;
 13     int ans;
 14     int change_or;
 15     int change_and;
 16 } PATCH;
 17 
 18 typedef struct
 19 {
 20     int to;
 21     int time;
 22     int next;
 23 } EDGE;
 24 
 25 int n,m;
 26 int v[1100000];
 27 bool inq[1100000];
 28 long long d[1100000];
 29 EDGE e[110000000];
 30 PATCH p[105];
 31 
 32 int main()
 33 {
 34     int kase=0;
 35 
 36     while(scanf("%d %d",&n,&m)==2&&(n||m))
 37     {
 38         kase++;
 39         char s1[30],s2[30];
 40         for(int i=0;i<m;i++)
 41         {
 42             scanf("%d %s %s",&p[i].time,s1,s2);
 43             p[i].test=p[i].ans=0;
 44             for(int j=0;j<n;j++)
 45             {
 46                 p[i].test=p[i].test*2+((s1[j]=='+'||s1[j]=='-')?1:0);
 47                 p[i].ans=p[i].ans*2+(s1[j]=='+'?1:0);
 48             }
 49             p[i].change_and=p[i].change_or=0;
 50             for(int j=0;j<n;j++)
 51             {
 52                 p[i].change_or=p[i].change_or*2+(s2[j]=='+'?1:0);
 53                 p[i].change_and=p[i].change_and*2+(s2[j]=='-'?0:1);
 54             }
 55         }
 56 
 57         memset(v,-1,sizeof(v));
 58 
 59         int t=0;
 60         for(int i=(1<<n)-1;i>0;i--)
 61         {
 62             for(int j=0;j<m;j++)
 63             {
 64                 if((i&p[j].test)==p[j].ans)
 65                 {
 66                     int w=i;
 67                     w|=p[j].change_or;
 68                     w&=p[j].change_and;
 69                     if(w!=i)
 70                     {
 71                         e[t].to=w;
 72                         e[t].time=p[j].time;
 73                         e[t].next=v[i];
 74                         v[i]=t;
 75                         t++;
 76                     }
 77                 }
 78             }
 79         }
 80 
 81         queue<int> q;
 82         q.push((1<<n)-1);
 83         memset(inq,false,sizeof(inq));
 84         for(int i=0;i<((1<<n)-1);i++)
 85             d[i]=INF;
 86         inq[(1<<n)-1]=true;
 87         d[(1<<n)-1]=0;
 88 
 89         while(!q.empty())
 90         {
 91             int i=q.front();
 92             int w=v[i];
 93             while(w!=-1)
 94             {
 95                 int j=e[w].to;
 96                 if(d[j]>d[i]+e[w].time)
 97                 {
 98                     d[j]=d[i]+e[w].time;
 99                     if(!inq[j])
100                     {
101                         q.push(j);
102                         inq[j]=true;
103                     }
104                 }
105                 w=e[w].next;
106             }
107             inq[i]=false;
108             q.pop();
109         }
110 
111         printf("Product %d
",kase);
112         if(d[0]==INF)
113             puts("Bugs cannot be fixed.
");
114         else
115             printf("Fastest sequence takes %lld seconds.

",d[0]);
116     }
117 
118     return 0;
119 }
[C++]
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/lzj-0218/p/3556415.html