网络流24题之十二 软件补丁问题

填坑

地址：luogu2761

题目描述

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 个错误属于 B21[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。

输入输出样例

3 3
1 000 00-
1 00- 0-+
2 0-- -++

8

模型

求一个状态到另一个状态变换的最少费用，最短路径问题。

实现

软件的状态用二进制位表示，第i位为第i个错误是否存在。把每个状态看做一个顶点，一个状态应用一个补丁到达另一状态，连接一条权值为补丁时间的有向边。求从初始状态到目标状态的最短路径即可。

代码：

#include <cstdio>
#include <queue>
#include <cstring>
#define N 4000000
#define INF 0x33333333
using namespace std;
struct packs
{
    int with,without;
    int rep,add;
    int w;
}pack[N];
int vis[N],m,n,dis[N];
queue<int>que;
int judge(int x,int y)
{
    if ((x|pack[y].with)!=x) return 0;
    if (x&pack[y].without) return 0;
    return 1;
}
void spfa(int S)
{
    memset(dis,0x33,sizeof dis);
    memset(vis,0,sizeof vis);
    que.push(S),vis[S]=1,dis[S]=0;
    while(!que.empty())
    {
        int now=que.front();que.pop();vis[now]=0;
        for (int i=1;i<=m;i++)
            if (judge(now,i))
            {
                int to=(now^(now&pack[i].add))|pack[i].rep;
                if (dis[to]>dis[now]+pack[i].w)
                {
                    dis[to]=dis[now]+pack[i].w;
                    if (!vis[to])
                        vis[to]=1,que.push(to);
                }
            }
    }
}
main()
{
    scanf("%d%d",&n,&m);
    char s[100];
    for (int i=1;i<=m;i++)
    {
        scanf("%d%s",&pack[i].w,s);
        for (int j=0;j<n;j++)
        {
            if (s[j]=='+')
                pack[i].with|=(1<<j);
            if (s[j]=='-')
                pack[i].without|=(1<<j);
        }
        scanf("%s",s);
        for (int j=0;j<n;j++)
        {
            if (s[j]=='+')
                pack[i].rep|=(1<<j);
            if (s[j]=='-')
                pack[i].add|=(1<<j);
        }
    }
    n=(1<<n)-1;//n个1
    spfa(n);
    if (dis[0]!=INF) printf("%d\n",dis[0]);
    else printf("0\n");
}