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

作者: MayFlyyh 分类: 网络流 发布时间: 2018-06-29 13:21 ė 6 2条评论

【网络流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;
}

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/247

2条评论

  1. Megumi 2018年7月8日 下午5:47 回复

    orzorzorzorz

  2. jjikkollp 2018年7月3日 下午4:18 回复

    orzorzorzorzorz

发表评论

电子邮件地址不会被公开。

Captcha Code

Ɣ回顶部