[UVA][sssp] 658 - It's not a Bug, it's a Feature!
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
in their software. And they have
released m patches
.
To apply patch pi to the
software, the bugs
have to be present in the software, and
the bugs
must be absent (of course
holds). The patch then
fixes the bugs
(if they have been present) and introduces
the new bugs
(where, again,
).
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 integers n and m, the number of bugs and patches, respectively. These values satisfy
and
.
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
先說明，位元運算是為了加速判斷，否則很容易 TLE。
題目描述：
現在有全部的 BUG，然而要安裝補丁使得 BUG 全部移除，每個補丁都有其特性，因此安裝的時間也會不同，
求最少時間將所有 BUG 移除。
補丁特性：原本的某些 BUG 要已經被修正(-)，某些 BUG 要存在(+)，
修正完後會產生某些 BUG(+)，已即移除某些 BUG(-)
題目解法：
n <= 20, 使用 bitmask，判斷是否可以使用補丁也都是使用 bitmask。
將起點壓成 20 bit 得狀態，每個 1/0 表示該 BUG 是否存在。
接著這裡使用 spfa 進行更新。
#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;
int n, m;
int sec[105], bplus[105], bminus[105], pplus[105], pminus[105];
int dist[1048576], inq[1048576];//2^20
void spfa() {
int i, j, k, tn, y;
queue<int> Q;
for(i = (1<<n)-1; i >= 0; i--)
dist[i] = 0xfffffff, inq[i] = 0;
dist[(1<<n)-1] = 0;
Q.push((1<<n)-1);// binary 1 as bug
while(!Q.empty()) {
tn = Q.front(), Q.pop();
inq[tn] = 0;
for(i = 0; i < m; i++) {
if((tn&bminus[i]) == 0 && (tn&bplus[i]) == bplus[i]) {//apply
y = tn|pplus[i];
y = y^(y&pminus[i]);
//printf("%d) %d -> %d\n", i, tn, y);
if(dist[y] > dist[tn] + sec[i]) {
dist[y] = dist[tn] + sec[i];
if(inq[y] == 0) {
inq[y] = 1;
Q.push(y);
}
}
}
}
}
if(dist[0] != 0xfffffff)
printf("Fastest sequence takes %d seconds.\n", dist[0]);
else
puts("Bugs cannot be fixed.");
}
int main() {
char bb[50], pp[50];
int i, j, k;
int cases = 0;
while(scanf("%d %d", &n, &m) == 2 && n) {
for(i = 0; i < m; i++) {
scanf("%d %s %s", &sec[i], &bb, &pp);
bplus[i] = bminus[i] = pplus[i] = pminus[i] = 0;
for(j = 0; j < n; j++) {
if(bb[j] == '+') bplus[i] |= 1<<j;
if(bb[j] == '-') bminus[i] |= 1<<j;
if(pp[j] == '+') pplus[i] |= 1<<j;
if(pp[j] == '-') pminus[i] |= 1<<j;
}
}
printf("Product %d\n", ++cases);
spfa();
puts("");
}
return 0;
}