网络流24题（十二）

2024-04-03 08:33:48

网络流24题（十二）

十二、软件补丁问题

题目描述

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

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

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

输入格式

第 1 行有 2 个正整数 n 和 m，n 表示错误总数，m表示补丁总数，1<=n<=20, 1<=m<=100。

接下来 m 行给出了 m 个补丁的信息。每行包括一个正整数，表示运行补丁程序 i 所需时间，以及 2 个长度为 n 的字符串，中间用一个空格符隔开。

第 1 个字符串中，如果第 k 个字符 bk 为“+”，则表示第 k 个错误属于 B1[i]，若为“-”，则表示第 k 个错误属于 B2[i]，若为“0”，则第 k 个错误既不属于 B1[i]也不属于 B2[i]，即软件中是否包含第 k 个错误并不影响补丁 i 的可用性。

第 2 个字符串中，如果第 k 个字符 bk为“-”，则表示第 k 个错误属于 F1[i]，若为“+”，则表示第 k 个错误属于 F2[i]，若为“0”，则第 k 个错误既不属于 F1[i]也不属于 F2[i]，即软件中是否包含第 k 个错误不会因使用补丁i 而改变。

输出格式

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

题解

模型：

状压最短路

建图与实现：

对于每一个错误都有被修复和修复两种情况，考虑二进制状压。每一位都错就是初始状态全1，目标状态全0。
考虑状态的转移（其实就是一个字符串处理），对于每一种给出的补丁可以理解为从一种状态转移到另外一种状态。（注意是一种，不是一个，所以需要枚举补丁）

然后跑最短路就行了。

代码

#include <iostream>
#include <queue>
#include <cstring>
#include <map>
#include <stack>
#define ll long long

const ll N = (1<<20)+50,M = 150;
const ll inf = 0x3f3f3f3f;
using namespace std;
struct Edge{
    ll w;
    string b,f;
}edge[M];
struct node{
    ll id,dis;
    bool operator < (const node &x)const{
        return dis > x.dis;
    }
};
ll n,m,s,t;
ll mov(ll x,Edge eg){
    for(ll tmp = x,cnt = 0;cnt<n;cnt++,tmp>>=1){
        ll pos = n-cnt-1;
        if(eg.b[pos] == '0' || (eg.b[pos] == '-' && (tmp&1) == 0) || (eg.b[pos] == '+' && (tmp&1) == 1)){
            if(eg.f[pos] == '0')continue;
            if(eg.f[pos] == '+')x = x|(1<<cnt);
            if(eg.f[pos] == '-')x = x&~(1<<cnt);
        }
        else return -1;
    }
    return x;
}
priority_queue<node> q;
bool done[N];
ll d[N];
void dij(){
    for(ll i = 0;i <= s;i++){
        d[i] = (i==s)?0:inf;
        done[i] = false;
    }
    //done[s] = true;
    q.push({s,d[s]});
    while(!q.empty()){
        node x = q.top();q.pop();
        //cout<<x.id<<' '<<x.dis<<endl;
        if(done[x.id]) continue;
        done[x.id] = true;
        for(ll i = 1;i <= m;i++){
            ll v = mov(x.id,edge[i]);
            //cout<<x.id<<' '<<i<<' '<<v<<endl;
            if(v == -1||done[v])continue;
            if(d[v] > x.dis+edge[i].w){
                d[v] = x.dis+edge[i].w;
                q.push({v,d[v]});
            }
        }
    }
    d[t] = d[t] == inf?0:d[t];
    cout<<d[t]<<endl;
}
int main() {
    cin>>n>>m;
    for(ll i = 1;i <= m;i++){
        cin>>edge[i].w>>edge[i].b>>edge[i].f;
    }
    s = (1<<n)-1,t = 0;
    dij();
    return 0;
}

码农公寓