题解 P2761 【软件补丁问题】

· · 题解

状压 + 最短路板子题（似乎不状压都可以过）。但感觉楼下的几位都讲的不是太详细，于是决定补发一波萌新友好型题解。适合还没有怎么接触过状态压缩和状态最短路的童鞋们。

如果你还不熟悉位运算六大运算符（&,|,~,^,<<,>>），可以先自行百度。

Step1. 怎么最短路？

这道题可能和平常我们熟知的最短路不太一样。节点不是现成的节点，边不是现成的边。

那么这道题中的节点是什么呢？是状态。状态就是指bug修复的状态。最开始，所有bug都还没有被修复，因此初始状态是 全部未修复 。通过运行某些补丁包，可以修复一些bug或者新增一些bug，那么此时的bug修复状态就是当前状态。我们就可以用最短路算法来维护从初始状态（全bug）到当前状态（修复了某些bug） 的最短路径。
你可能还会问，我们怎么加边呢？这道题不需要加边，每次只需要枚举每一个补丁包即可（类似于完全图）
那路径长度是什么呢？不就是运行补丁包的总时间吗。
终点是什么呢？很显然，就是修复全部的Bug。

Step2. 状态压缩

由于一共有最多20个bug，如果每个bug都有已经修复和没有修复两种状态，那么每次状态转移需要传20个参（20元数组）。能不能把这一过程优化到1个参数呢？我们需要状态压缩。由于对于每个bug都只有修复没修复两种状态，我们不妨用0,1表示（1表示未修复，0已修复）。如果我们把这20个0,1串在一起就得到了一个二进制串，一个二进制串也就对应着一个整数。这样我们就把一个状态压缩成了一个整数(int)
我们以样例为例，假设当前一种状态是（已修复bug12，未修复bug3），那么对应的01串就是110，转化成整数就是6。那么我们就可以知道：初始的bug全部未修复状态为111，对应7。结束的bug全部修复状态为000，对应0。将情况拓展到 n 个bug，那么初始状态就是 2^n-1，即(1<<n)-1。结束状态是 0。

Step3. 状态转移

说完了压缩再来说说转移。转移说白了就是根据当前的状态，计算出修复了bug之后的状态。

判断能否使用一个补丁包

翻译成状态语言就是，只有当前状态的某些位置上全部是1，某些位置上全部是0，才可以运行补丁包。如何进行这一判断呢？ 我们可以把一个补丁包的使用先决条件也压缩成两条状态。样例中补丁包3的使用条件b1就是000=0，b2就是011=3.

记当前状态为x
1.判断是不是所有的b1位都是1：我们可以把b1与x按位与。容易知道，如果的得到的值就是b1本身，那么x所有b1位上都是1
2.判断是不是所有的b2位都是0：我们可以把b1与x按位与。容易知道，如果的得到的值就是0，那么now所有b2位上都是0

代码：（p是补丁包结构体）

 if((x&p[i].b1)==p[i].b1&&(x&p[i].b2)==0) 执行下一步

使用了一个补丁之后的情况

翻译成状态语言就是，使用之后将f1位置上变成0,f2位置上变成1。我们还是按照之前的思路，将f1,f2也计算成两个状态。如果需要将f2位置变成1，那么只需要用当前状态或上f2。如果需要将f1位置变成0，我们可以或上一个f1，使得当前状态的所有f1位置都变成1，再异或一个f1，这样就可以将f1所有位置变成0.

代码：（y代表运行补丁包之后的状态）

 int y=((x|p[i].f1)|p[i].f2)^p[i].f1;

Step 4. 贯穿

主要思路讲完了，接下来就是完整的代码。

 #include<cstdio>
#include<queue>
#include<cstring>
using namespace std;

struct pack{int f1,f2,b1,b2,t;}p[505];
int n,m,fir,minn[1<<22],tag;  //由于最多有2^20种状态，数组要开够
queue<int>q;bool exi[1<<22];

inline void read(int &x){
    char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    x=ch^48;ch=getchar();
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
}

inline int gtag(){  //手写读入可以防止出错
    char ch=getchar();
    while(ch!='+'&&ch!='-'&&ch!='0')ch=getchar();
    if(ch=='+')return 1;
    if(ch=='-')return 2;
    return 0;
}

void spfa(){  //关于spfa，它还没死
    memset(minn,0x7f,sizeof(minn));
    minn[fir]=0;
    q.push(fir);
    while(!q.empty()){
        int x=q.front();
        for(int i=1;i<=m;++i)  //枚举每一个包
         if((x&p[i].b1)==p[i].b1&&(x&p[i].b2)==0){  //判断先决
            int y=((x|p[i].f1)|p[i].f2)^p[i].f1;//得到运行后状态
            if(minn[x]+p[i].t<minn[y]){
                minn[y]=minn[x]+p[i].t;
                if(!exi[y]){
                    q.push(y);
                    exi[y]=true;
                }
            }
         }
        exi[x]=false;
        q.pop();
    }
}

int main(){
    read(n);read(m);
    for(int i=1;i<=m;++i){
        read(p[i].t);
        for(int j=1;j<=n;++j){
            tag=gtag();
            if(tag==1)p[i].b1|=(1<<j-1);  
            if(tag==2)p[i].b2|=(1<<j-1);  //得到每个补丁包的先决条件串
        }
        for(int j=1;j<=n;++j){
            tag=gtag();
            if(tag==1)p[i].f2|=(1<<j-1);
            if(tag==2)p[i].f1|=(1<<j-1);  //得到每个补丁包运行之后的状态串
        }
    }
    fir=(1<<n)-1;   //得到初始状态
    spfa();
    if(minn[0]==minn[(1<<22)-1])printf("0");  //如果根本到达不了目标状态，就是无解
     else printf("%d",minn[0]); 
    return 0;
}