传送门 ↬\looparrowright

题目描述

T\text T 公司发现其研制的一个软件中有 nn 个错误，随即为该软件发放了一批共 mm 个补丁程序。每一个补丁程序都有其特定的适用环境，某个补丁只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用。一个补丁在排除某些错误的同时，往往会加入另一些错误。
换句话说，对于每一个补丁 ii，都有 22 个与之相应的错误集合 b1b_1和 b2b_2，使得仅当软件包含 b1b_1 中的所有错误，而不包含 b2b_2 中的任何错误时，才可以使用补丁 ii。补丁 ii 将修复软件中的某些错误 f1f_1，而同时加入另一些错误 f2f_2。另外，每个补丁都耗费一定的时间。
试设计一个算法，利用 T\text T 公司提供的 mm 个补丁程序将原软件修复成一个没有错误的软件，并使修复后的软件耗时最少。对于给定的 nn 个错误和 mm 个补丁程序，找到总耗时最少的软件修复方案。

输入格式

第 11 行有 22 个正整数 nn 和 mm，nn 表示错误总数，mm 表示补丁总数，1⩽n⩽201\leqslant n\leqslant20，1⩽m⩽1001\leqslant m\leqslant 100。
接下来 mm 行给出了 mm 个补丁的信息。每行包括一个正整数，表示运行补丁程序 ii 所需时间，以及 22 个长度为 nn 的字符串，中间用一个空格符隔开。
第 11 个字符串中，如果第 kk 个字符为 +，则表示第 kk 个错误属于 b1b_1，若为 -，则表示第 kk 个错误属于 b2b_2，若为 0，则第 kk 个错误既不属于 b1b_1 也不属于 b2b_2，即软件中是否包含第 kk 个错误并不影响补丁 ii 的可用性。
第 22 个字符串中，如果第 kk 个字符为 -，则表示第 kk 个错误属于 f1f_1，若为 +，则表示第 kk 个错误属于 f2f_2，若为 0，则第 kk 个错误既不属于 f1f_1 也不属于 f2f_2，即软件中是否包含第 kk 个错误不会因使用补丁 ii 而改变。

输出格式

程序运行结束时，将总耗时数输出。如果问题无解，则输出 0。

输入输出样例

输入 #1

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

输出 #1

8

分析

定义整数 statestate 表示当前软件中包含错误的状态。错误个数的上限为 2020，不妨采用状态压缩的方式，将 statestate 拆成 2020 位二进制数，若第 kk 位为 11，表示当前软件中包含第 k+1k+1 个错误，其中 k∈N∗k\in\mathbb N^\ast 且 0⩽k⩽190\leqslant k\leqslant 19。我们的任务是要将状态 2n−12^n-1 用最短的时间变为状态 00。使用一个补丁，即可完成一次状态转移，每次状态转移的代价为该补丁消耗的时间，由于代价各不相同，可以考虑使用 SPFA\text{SPFA} 算法求最小代价。
接下来讨论如何进行状态转移。
首先要考虑，当前状态为 xx 时，如何判断一个补丁可用，可用的条件已经给出：包含 b1b_1 中所有错误，不包含 b2b_2 中任何错误。同样的，可以将 b1,b2b_1,b_2 进行状态压缩，若字符串第 kk 位为 +，则 b1b_1 第 k−1k-1 位为 11，否则为 00；若字符串第 kk 位为 -，则 b2b_2 第 k−1k-1 位为 11，否则为 00；其中，k∈N∗k\in\mathbb N^\ast 且 1⩽k⩽201\leqslant k\leqslant 20。举例：对于第三个补丁，b1=(000)2=0b_1=(000)_2=0，b2=(011)2=6b_2=(011)_2=6。定义集合 $\mathbb F=\{p\in\mathbb N^\ast|0\leqslant p\leqslant 19,b_{1p}=1\}$，$\mathbb G=\{p\in\mathbb N^\ast|0\leqslant p\leqslant 19,b_{2p}=1\}$；当且仅当 ∀ r∈F,s∈G\forall\ r\in\mathbb F,s\in\mathbb G，有 xr=1,xs=0x_r=1,x_s=0 时，这个补丁才可以使用；其中，p,r,sp,r,s 为二进制位的编号。∀ r∈F\forall\ r\in\mathbb F，xr=1x_r=1 的充要条件为 x∧b1=b1x\wedge b_1=b_1；∀ s∈G\forall\ s\in\mathbb G，xs=0x_s=0 的充要条件为 x∨b2=0x\vee b_2=0。因此，当且仅当 x∧b1=1x\wedge b_1=1 且 x∨b2=0x\vee b_2=0 时，这个补丁可用。
当补丁可用，就要修改当前状态 xx。同样要将 f1f_1 和 f2f_2 进行状态压缩。若字符串第 kk 位为 -，则 f1f_1 第 k−1k-1 位为 11，否则为 00；若字符串第 kk 位为 +，则 f2f_2 第 k−1k-1 位为 11，否则为 00；其中，k∈N∗k\in\mathbb N^\ast 且 1⩽k⩽201\leqslant k\leqslant 20。举例：对于第三个补丁，$f_1=(100)_2=4$，$f_2=(011)_2=6$。将状态 xx 修改为状态 yy，需要进行三步操作：① 令 y=xy=x；② ∀ r∈N∗\forall\ r\in\mathbb N^\ast 且 0⩽r⩽190\leqslant r\leqslant 19，若 f1r=1f_{1r}=1，则令 yr=0y_r=0；③ ∀ s∈N∗\forall\ s\in\mathbb N^\ast 且 0⩽s⩽190\leqslant s\leqslant19，若 f2s=1f_{2s}=1，则令 ys=1y_s=1。完成操作①，直接赋值即可；完成操作②，可先作或运算，若 f1r=1f_{1r}=1，那么 yry_r 都变成 11，再进行异或运算，yry_r 都变为 00，即 (y∨f1)⊕f1(y\vee f_1)\oplus f_1；完成操作③，直接作或运算即可，即 y∨f2y\vee f_2。所以，由状态 xx 转移到 yy，有关系式 y=(x∨f1)⊕f1∨f2y=(x\vee f_1)\oplus f_1\vee f_2。
运行 SPFA\text{SPFA} 算法时，从对头取出状态 xx，遍历 mm 个补丁，若补丁可以使用，则进行状态转移得到新的状态 yy。进行多次松弛操作后，可以得到状态 2n−12^n-1 转移至状态 00 的最小代价。

代码

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: 洛谷 P2761
Date: 8/2/2020
Description: State Compression and SPFA
*******************************************************************/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
const int N=21;
const int M=102;
const int inf=0x3f3f3f3f;
struct CPatch
{
	int t;//时间
	int b1;//包括的错误
	int b2;//不包括的错误
	int f1;//修改的错误
	int f2;//产生的错误
}patch[M];
bool inqueue[1<<N];
int dis[1<<N];
int n,m;
char str[N];
int SPFA(int,int);
int main()
{
	cin>>n>>m;
	int i,j;
	for(i=1;i<=m;i++)
	{
		scanf("%d",&patch[i].t);
		scanf("%s",str+1);//读入b
		//状态压缩
		for(j=1;j<=n;j++)
		{
			//b1为 +
			//b2为 -
			if(str[j]=='+') patch[i].b1|=(1<<j-1);
			if(str[j]=='-') patch[i].b2|=(1<<j-1);
		}
		scanf("%s",str+1);
		for(j=1;j<=n;j++)
		{
			//f1为 -
			//f2为 +
			if(str[j]=='-') patch[i].f1|=(1<<j-1);
			if(str[j]=='+') patch[i].f2|=(1<<j-1);
		}
	}
	cout<<SPFA((1<<n)-1,0)<<endl;
	return 0;
}
int SPFA(int s,int t)
{
	memset(dis,inf,sizeof(dis));
	dis[s]=0;
	queue<int>q;
	q.push(s);
	inqueue[s]=1;
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		inqueue[x]=0;
		for(register int i=1;i<=m;i++)
		{
			//可以使用补丁 patch[i]
			if((x&patch[i].b1)==patch[i].b1&&(x&patch[i].b2)==0)
			{
				//运行补丁后状态
				int y=(x|patch[i].f1)^patch[i].f1)|patch[i].f2;
				if(dis[x]+patch[i].t<dis[y])
				{
					dis[y]=dis[x]+patch[i].t;
					if(!inqueue[y])
					{
						q.push(y);
						inqueue[y]=1;
					}
				}
			}
		}
	}
	return dis[t]==inf?0:dis[t];
}