【网络流24题----12】软件补丁问题

软件补丁问题

Description

T 公司发现其研制的一个软件中有 n 个错误，随即为该软件发放了一批共 m 个补丁程序。
每一个补丁程序都有其特定的适用环境，某个补丁只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用。
一个补丁在排除某些错误的同时，往往会加入另一些错误。
换句话说，对于每一个补丁 i，都有 2 个与之相应的错误集合 B1[i] 和 B2[i]，使得仅当软件包含 B1[i] 中的所有错误，而不包含 B2[i] 中的任何错误时，才可以使用补丁 i。
补丁 i 将修复软件中的某些错误 F1[i]，而同时加入另一些错误 F2[i]。
另外，每个补丁都耗费一定的时间。
试设计一个算法，利用 T 公司提供的 m 个补丁程序将原软件修复成一个没有错误的软件，并使修复后的软件耗时最少。

对于给定的 n 个错误和 m 个补丁程序，找到总耗时最少的软件修复方案。

Input

第 1 行有 2 个正整数 n 和 m，n 表示错误总数，m 表示补丁总数，1<=n<=20,1<=m<=100。
接下来 m 行给出了 m 个补丁的信息。
每行包括一个正整数，表示运行补丁程序 i 所需时间，以及 2 个长度为 n 的字符串，中间用一个空格符隔开。
第 1 个字符串中，如果第 k 个字符 bk 为“+” ，则表示第 k 个错误属于 B1[i]，若为“-”，则表示第 k 个错误属于 B2[i]，若为“0” ，则第 k 个错误既不属于 B1[i] 也不属于 B2[i]，即软件中是否包含第 k 个错误并不影响补丁 i 的可用性。
第 2 个字符串中，如果第 k 个字符 bk 为“-”1 ，则表示第 k 个错误属于 F1[i]，若为“+”，则表示第 k 个错误属于 F2[i]，若为“0” ，则第 k 个错误既不属于 F1[i] 也不属于 F2[i]，即软件中是否包含第 k 个错误不会因使用补丁 i 而改变。

Output

将总耗时数输出。如果问题无解，则输出 0。

Sample Input

3 3
1 000 00-
1 00- 0-+
2 0– -++

Sample Output

8

24题中的最后一个分层图最短路了，注意一下就是有的OJ上题目有误(f1，f2搞反了)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<vector>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<cstring>
 8 using namespace std;
 9 #define maxn 110
10 #define SIZE 2000000
11 #define inf (llg)1e16
12 #define llg long long 
13 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
14 llg n,m,tail,head,dl[SIZE+10],dis[(1<<20)+10],bj[(1<<20)+10];
15 char s[maxn];
16 
17 struct node
18 {
19     llg dis,b1,b2,f1,f2;
20 }a[maxn];
21 
22 void init()
23 {
24     cin>>n>>m;
25     for (llg i=0;i<(1<<n)-1;i++) dis[i]=inf;
26     for (llg i=1;i<=m;i++)
27     {
28         scanf("%lld",&a[i].dis);
29         scanf("%s",s);
30         for (llg k=0;k<n;k++)
31         {
32             if (s[k]=='+') a[i].b1+=(1<<k);
33             if (s[k]=='-') a[i].b2+=(1<<k);
34         }
35         scanf("%s",s);
36         for (llg k=0;k<n;k++)
37         {
38             if (s[k]=='-') a[i].f1+=(1<<k);
39             if (s[k]=='+') a[i].f2+=(1<<k);
40         }
41     }
42     tail=1; head=0; dl[1]=(1<<n)-1;
43 }
44 
45 void spfa()
46 {
47     llg x,v;
48     do
49     {
50         head%=SIZE; head++;
51         x=dl[head]; bj[x]=0;
52         for (llg i=1;i<=m;i++)
53             if (((x|a[i].b1)==x) && ((x&a[i].b2)==0))
54             {
55                 v=x;
56                 for (llg k=0;k<n;k++) if ((v&(1<<k)) && (a[i].f1&(1<<k))) v^=(1<<k);
57                 v|=a[i].f2;
58                 if (dis[v]>dis[x]+a[i].dis)
59                 {
60                     dis[v]=dis[x]+a[i].dis;
61                     if (!bj[v])
62                     {
63                         bj[v]=1;
64                         tail%=SIZE; tail++;
65                         dl[tail]=v;
66                     }
67                 }
68             }
69     }while (head!=tail);
70 }
71 
72 int main()
73 {
74     yyj("a");
75     init();
76     spfa();
77     if (dis[0]==inf) cout<<0;else cout<<dis[0];
78     return 0;
79 }