题解：UVA658 这不是bug，而是特性 It's not a Bug, it's a Feature!

· · 题解

思路

在任意时刻，枚举补丁看是否能用当前补丁，如果符合当前补丁使用的状态，就使用补丁进行修补。

记得用二进制表示打补丁之前与打上补丁之后的状态。

代码

#include<bits/stdc++.h>
using namespace std;
template<typename T>void read(T&x)
{
    x = 0;char c;int sign = 1;
    do { c = getchar(); if(c == '-') sign = -1; }while(!isdigit(c));
    do { x = x * 10 + c - '0'; c = getchar(); }while(isdigit(c));
    x *= sign;
}
const int N = 1 << 20; 
int n,m,s,a[N],b[N],c[N],d[N];
long long dis[N],t[N];

priority_queue<pair<long long,int> > q; 
void SPFA()
{
    memset(dis,0x3f,sizeof dis);
    dis[s] = 0; q.push(make_pair(0,s));
    while(!q.empty())
    {
        int x = q.top().second; q.pop();
        for(int i = 1;i <= m; ++ i)
            if(((x&a[i]) == a[i]) && (x&b[i])==0) // 表示 x 是否能打上补丁i a[i]表示打补丁前有bug的位置 b[i]表示打补丁前没bug的位置 
            {
                int y = (x|c[i])&d[i]; // 表示x打上补丁后的状态 c[i]打补丁后有bug的位置  d[i]打补丁后没bug的位置 
                if(dis[y] > dis[x] + t[i])
                {
                    dis[y] = dis[x] + t[i];
                    q.push(make_pair(-dis[y],y));
                }
            }
    }
}

int main()
{
    for(int k = 1;;k++)
    {
        read(n); read(m);
        if(n == 0 && m == 0) break; 
        cout << "Product " << k << endl;
        s = (1 << n) - 1; 
        for(int i = 1;i <= m; ++ i)
        {
            string c1,c2;
            cin >> t[i] >> c1 >> c2;
            a[i] = 0; b[i] = 0; c[i] = 0; 
            for(int j = 0;j < n; ++ j)
                if(c1[j] == '+')
                    a[i] |= (1 << j);
                else if(c1[j] == '-')
                    b[i] |= (1 << j);
            d[i] = s;
            for(int j = 0;j < n; ++ j)
                if(c2[j] == '+')
                    c[i] |= (1 << j);
                else if(c2[j] == '-')
                    d[i] ^= (1 << j);
        }
        SPFA(); 
        if(dis[0] == 0x3f3f3f3f3f3f3f3f)
            cout << "Bugs cannot be fixed." << endl;
        else cout << "Fastest sequence takes "<< dis[0] << " seconds." << endl;
        cout << endl; 
     } 
    return 0;
}