【网络流24题】软件补丁问题

【网络流24题】软件补丁问题

T 公司发现其研制的一个软件中有 n 个错误，随即为该软件发放了一批共 m 个补丁程序。每一个补丁程序都有其特定的适用环境，某个补丁只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用。一个补丁在排除某些错误的同时，往往会加入另一些错误。

换句话说，对于每一个补丁 i，都有 2 个与之相应的错误集合 B1[i]和 B2[i]，使得仅当软件包含 B1[i]中的所有错误，而不包含 B2[i]中的任何错误时，才可以使用补丁 i。补丁 i 将修复软件中的某些错误 F1[i]，而同时加入另一些错误 F2[i]。另外，每个补丁都耗费一定的时间。

试设计一个算法，利用 T 公司提供的 m 个补丁程序将原软件修复成一个没有错误的软件，并使修复后的软件耗时最少。对于给定的 n 个错误和 m 个补丁程序，找到总耗时最少的软件修复方案。

状态压缩，运用位运算的技巧对每个状态进行转移（吧

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define ll long long 
const int N = 1<<21;
struct heap{
    int name;ll v; 
    bool operator < (const heap m) const{
        return v>m.v;
    }
};
int cnt;ll t[200];
int f1[200],f2[200],v[N],b1[200],b2[200];
char c[30];
ll dis[N];int n,m;
inline int DP(){
    std::priority_queue<heap> q;
    memset(dis,0x3f,sizeof(dis));
    while(!q.empty()) q.pop();
    q.push((heap){(1<<n)-1,0});
    dis[(1<<n)-1]=0;
    while(!q.empty()){
        heap now=q.top();q.pop();
        int x=now.name;
        if(v[x]) continue;
        v[x]=1;
        for(int i=1;i<=m;++i){
            if((x|b1[i])!=x) continue;
            if((x&b2[i])!=0) continue;
            int tmp=x;
            tmp|=f2[i];
            //if(f1[i]!=0)
            tmp&=(~f1[i]);
            if(dis[tmp]>dis[x]+t[i]){
                dis[tmp]=dis[x]+t[i];
                q.push((heap){tmp,dis[tmp]});
            }
        }
    }
}
int main (){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%lld",&t[i]);
        scanf(" %s",c);
        for(int j=0;j<n;++j){
            if(c[j]=='+'){b1[i]|=(1<<j);}
            if(c[j]=='-'){b2[i]|=(1<<j);}
        }
        scanf(" %s",c);
        for(int j=0;j<n;++j){
            if(c[j]=='-'){f1[i]|=(1<<j);}
            if(c[j]=='+'){f2[i]|=(1<<j);}
        }
    }
    DP();
    if(dis[0]==0x3f3f3f3f3f3f3f3f) dis[0]=0;
    printf("%lld",dis[0]);
    return 0;
}