[网络流24题] 软件补丁

发表于   |  

被标题坑了。。。

问题描述

对于一个软件公司来说，在发行一个新软件之后，可以说已经完成了工作。但是实际上，许多软件公司在发行一个新产品之后，还经常发送补丁程序，修改原产品中的错误(当然，有些补丁是要收费的)。
如某微硬公司就是这样的一个软件公司。今年夏天，在发行了一个新的字处理软件之后，到现在他们已经编写了许多补丁程序。仅仅在这个周末，他们就用新编写的补丁程序解决了软件中的一个大问题。而在每一个补丁程序修改软件中的某些错误时，有可能引起软件中原来存在的某些错误重新发作。发生这种情况是因为当修改一个错误时，补丁程序利用了程序中约定的特别行为，从而导致错误的重新产生。
微硬公司在他们的软件中一共发现了n个错误B={bl，b2，…，bn)，现在他们一共发送了m 个补丁程序p1,p2，…,pm。如果想要在软件中应用第pi号补丁程序，则软件中必须存在错误B+i ≤B，并且错误B-i≤B必须不存在(显然，B+i∩B-i为空集)。然后，这个补丁程序将改正错误 F-i≤B(如果错误存在的话)，并且产生新错误F+i≤B(同样，F+i∩F-i也为空集)。
现在，微硬公司的问题只有一个。他们给出一个原始版本的软件，软件包含了B中的所有错误，然后按照某一顺序在软件中应用补丁程序(应用某个补丁程序时，软件必须符合该补丁程序的应用条件，且运行该程序需要一定的时间)。问怎样才能最快地改正软件中的所有错误(即为修正所有错误而运行的补丁程序的总时间最短)?

输入格式

数据存放在当前目录下的文本文件“bugs.in””中。
文件的第一行包含两个整数n和m，分别表示软件中的错误个数和发送的补丁个数。其中，n和m满足条件：1≤n≤20，1≤m≤100。
接下来的m行(即第2行至第m+1行)按顺序描述了m个补丁程序的情况，第i行描述第i-1号补丁程序。每一行包含一个整数(表示在软件中应用该补丁程序所需的时间，单位为秒)和两个n个字符的字符串(中间均用一个空格分开)。、
第一个字符串描述了应用该补丁程序(第i-1号)的条件，即说明在软件中某错误应该存在还是不应该存在。字符串的第i个字符，如果是“+”，表示在软件中必须存在bi号错误；如果是“-”，表示软件中错误bi不能存在；如果是“0””，则表示错误bi存在或不存在均可(即对应用该补丁程序没有影响)。
第二个字符串描述了应用该补丁程序(第i-1号)后的效果，即应用补丁程序后，哪些错误被修改好了，而又产生了哪些新错误。字符串的第i个字符，如果是“+”，表示产生了一个新错误bi；如果是“-”，表示错误bi被修改好了；如果是“0”，则表示错误bi不变(即原来存在，则仍然存在；原来不存在，则也不存在)。

输出格式

答案输出在当前目录下的文本文件“bugs.out””中。
请你找到一个应用补丁程序的最优顺序，修改软件中的所有错误，并且所用的时间最少。
注意，每个补丁程序是可以应用多次的。
如果存在这样一个序列，请在输出文件的第一行输出应用补丁程序的总时间(单位为秒)；如果找不到这样一个序列，请在输出文件的第一行输出-1。

输入输出样例

样例输入（bugs.in）:
3 3
1 000 00-
1 00- 0-+
2 0– -++
样例输出（bugs.out）：
8

Sol

与网络流无关

只有20个补丁，很容易想到状态压缩。
最多(1<<20)个状态，一个状态到另一个状态间有一个花费。
求最短花费，就是最短路了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define maxn 1049000
#define maxm 120
using namespace std;
struct Path
{
	int p1, p2, q1, q2, dis;
}p[maxm];
int dis[maxn], n, m;
bool bo[maxn];
queue <int> q;
bool spfa(int src){
	memset(dis, 127, sizeof dis);
	int MAX = dis[0];
	q.push(src);
	dis[src] = 0;
	bo[src] = true;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		bo[u] = false;
		for (int i = 1; i <= m; i++) 
			if ((p[i].p1 & u) == p[i].p1 && (p[i].p2 & u) == 0){
				int v = (u | p[i].q1) & (~p[i].q2) ;
				//printf(""%d %d %d %d %d\n"", u, v, i, p[i].q1, p[i].q2);
				if (dis[v] > dis[u] + p[i].dis) {
					dis[v] = dis[u] + p[i].dis;
					if (!bo[v]) {
						q.push(v);
						bo[v] = true;
					}
				}
			}
	}
	if (dis[0] < MAX) return true;
	return false;
}
int main(){
freopen(""bugs.in"",""r"",stdin);
freopen(""bugs.out"",""w"",stdout);
	scanf(""%d%d"", &n, &m);
	for (int i = 1; i <= m; i++){
		char a[21],b[21];
		scanf(""%d %s %s"", &p[i].dis, a, b);
		for (int j = 0; j <= n-1; j++){
			if (a[j] == '+') p[i].p1 |= 1 << j;
			if (a[j] == '-') p[i].p2 |= 1 << j;
			if (b[j] == '+') p[i].q1 |= 1 << j;
			if (b[j] == '-') p[i].q2 |= 1 << j;
		}
		//printf(""%d %d %d %d\n"", p[i].q1, p[i].q2, p[i].p1, p[i].p2);
	}
	if (spfa((1 << n) - 1)) printf(""%d\n"", dis[0]);
	else printf(""-1\n"");
	return 0;
}