P2761 software patch

Title Description

T The company found n bugs in a software it developed and issued a batch of M patches for the software. Every patch has its own environment, and a patch can only be used if it contains some errors in the software without others. A patch inWhile eliminating certain mistakes, other mistakes are often added.

In other words, for each patch i, there are two corresponding error sets B1 [i] and B2 [i], making it possible to use patch I only if the software contains all the errors in B1 [i] and not any errors in B2 [i]. Patch I will be repairedSome errors in complex software F1[i] are added, while some other error F2[i] is added. In addition, each patch takes a certain amount of time.

Try to design an algorithm, using M patches provided by T company to repair the original software into a software without errors, and make the repaired software take the least time. For a given n error and M patch, find the least time-consuming software repair plan.

1<=n<=20, 1<=m<=100

Problem analysis:

Because n is very small, we can use 0 and 1 to represent the state of each vulnerability, that is, the current system state is represented by a string of 01, state compression.

DPYes, but there are 1e6 species in the DP state. Each transfer takes m times, and the complexity is too large. So solving the problem with the shortest path can reduce some of the states that will not arrive.

The starting point is the state in which all vulnerabilities have not been repaired (11…. 11), and the ending point is the state in which all vulnerabilities have been repaired (00…. 00).

Code:

#include <bits/stdc++.h>
using namespace std;
char s[25];
int t[105];
int sta1[105],sta2[105];
int res1[105],res2[105];
int dis[2100000],vis[2100000];
queue<int> Q;
int main()
{
    memset(dis,0x3f,sizeof(dis));
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;++i){
        scanf("%d",&t[i]);
        scanf("%s",s);
        for(int j = 0;j < n;++j){
            if(s[j] == '+') sta1[i] += (1<<j);
            else if(s[j] == '-') sta2[i] += (1<<j);
        }
        scanf("%s",s);
        for(int j = 0;j < n;++j){
            if(s[j] == '+') res2[i] += (1<<j);
            else if(s[j] == '-') res1[i] += (1<<j);
        }
    }
    int now = (1<<n)-1;
    dis[now] = 0;
    Q.push(now);
    vis[now] = 1;
    while(!Q.empty()){
        now = Q.front();
        Q.pop();
    
        for(int i = 1;i <= m;++i){
            if((now & sta1[i]) != sta1[i]) continue;
            if((~now & sta2[i]) != sta2[i]) continue;
            int tmp = (now  & (~res1[i])) | res2[i];           
            if(dis[tmp] > dis[now] + t[i]){
                dis[tmp] = dis[now] + t[i];
                if(!vis[tmp]) vis[tmp] = 1,Q.push(tmp);
            }
        }
        vis[now] = 0;
    }
    if(dis[0] == 0x3f3f3f3f) puts("0");
    else printf("%d\n",dis[0]);
    return 0;
}