Patch
Problem description
There are always errors in a program. The company often releases patches to correct these errors. Unfortunately, when correcting some errors with each patch, some errors will be added at the same time. Each patch has a certain running time.
A company published a game with n errors B={b1,b2,b3,..., bn}, so the company released m patches. The application of each patch is conditional (that is, which errors must exist and which errors cannot exist).
Find out how much time it will take to correct all these errors.
input
There are two positive integers n and m in the first line of the input file. N represents the total number of errors, M represents the total number of patches, 1 ≤ n ≤ 20, 1 ≤ m ≤ 100. Next, line m gives the information of M patches. Each line includes a positive integer (representing the running time of this patch) and two strings,
The first string describes the conditions for applying the patch. The ith character of the string, if '+', indicates that there must be error No. bi in the software; If it is' - ', it means that the error bi in the software cannot exist; If it is' 0 ', it means that the error bi exists or does not exist (that is, it has no impact on the application of the patch).
The second string describes the effect of applying the patch. The ith of the string, if '+', indicates a new error bi; If it is' - ', it means that the error bi has been corrected; If it is' 0 ', it means that the error bi remains unchanged (that is, the original exists and still exists; the original does not exist or does not exist).
output
Output an integer. If the problem has a solution, the output will take a long time. Otherwise, output - 1.
Sample Input
3 5 1 0-+ -+- 3 +-- -00 4 000 00- 6 +0+ -0- 3 0+0 0-0
Sample Output
7
General idea of the topic
At first, there were many bugs. We marked the bug as +
So it started with + + +, and our goal is -
Each patch must meet the conditions before it can be used, but the patch will also cause new bugs. Then your task is to find an optimal solution to fix all bugs.
Train of thought analysis
This problem is mainly two knowledge points, one is state compression, the other is the use of spfa algorithm.
Here spfa can also use Dijkstra heap optimization method to complete the construction.
Because the graph here may or may not be formed between each point.
Therefore, we have to run all nodes violently for each exit to see if it can be connected, and then run directly with spfa
State compression is that the node of each character is nothing more than 0 or 1 We can open int and can store 32 to ensure that it is enough.
Next is the operation of bit operation.
It should be noted here that his position has a total of 220 possibilities
Accepted Code
//#include<unordered_map>
#include<algorithm>
#include<iostream>
#include<string.h>
#include <iomanip>
#include<stdio.h>
#include<vector>
#include<string>
#include<math.h>
#include<cmath>
#include<queue>
#include<stack>
#include<deque>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll ll_inf = 9223372036854775807;
const int int_inf = 2147483647;
const short short_inf = 32767;
const ll less_inf = 0x3f3f3f3f;
const char char_inf = 127;
#pragma GCC optimize(2)
#define accelerate cin.tie(NULL);cout.tie(NULL);ios::sync_with_stdio(false);
#define PI 3.141592653589793
#define EPS 1.0e-8
ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
return a / gcd(a, b) * b;
}
inline ll read() {
ll c = getchar(), Nig = 1, x = 0;
while (!isdigit(c) && c != '-')c = getchar();
if (c == '-')Nig = -1, c = getchar();
while (isdigit(c))x = ((x << 1) + (x << 3)) + (c ^ '0'), c = getchar();
return Nig * x;
}
inline void out(ll a) {
if (a < 0)putchar('-'), a = -a;
if (a > 9)out(a / 10);
putchar(a % 10 + '0');
}
ll qpow(ll x, ll n, ll mod) {
ll res = 1;
while (n > 0) {
if (n & 1)res = (res * x) % mod;
x = (x * x) % mod;
n >>= 1;
}
return res;
}
#define read read()
const int MAXN = 4000000, N = 105;
int n, m;
bool judge[MAXN];
int dis[MAXN];
int A[N], B[N], C[N], D[N], val[N];
queue<int>q;
void spfa(ll sta) {
memset(dis, 0x3f3f3f3f, sizeof(dis));
dis[sta] = 0;
q.push(sta);
while (q.size()) {
int x = q.front(), y;
q.pop();
judge[x] = false;
for (int i = 0; i < m; i++) {
if ((A[i] & x) == A[i] && (B[i] & x) == 0) {
y = ((x | C[i]) ^ C[i]) | D[i];
if (dis[x] + val[i] < dis[y]) {
dis[y] = dis[x] + val[i];
if (!judge[y])judge[y] = true, q.push(y);
}
}
}
}
}
int main()
{
n = read, m = read;
char a[50], b[50];
for (int i = 0; i < m; i++) {
scanf("%d%s%s", &val[i], a, b);
A[i] = B[i] = C[i] = D[i] = 0;
for (int j = 0; j < n; j++) {
if (a[j] == '+')A[i] |= (1 << j);
else if (a[j] == '-')B[i] |= (1 << j);
if (b[j] == '-')C[i] |= (1 << j);
else if (b[j] == '+')D[i] |= (1 << j);
}
}
spfa((1 << n) - 1);
out(dis[0] == 0x3f3f3f3f ? -1 : dis[0]);
puts("");
return 0;
}