9018: 软件补丁问题

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

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

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

程序运行结束时，将总耗时数输出到文件output.txt中。如果问题无解，则输出0。

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

8