题意分析

题目模拟软件补丁修复漏洞的过程：

• 初始状态：软件包含所有漏洞（n 个漏洞，编号 b1 到 bn）。
• 补丁规则：每个补丁 pi 有：
  • 应用条件：漏洞集合 Bi+ 必须存在，Bi- 必须不存在（Bi+ 和 Bi- 无交集）。
  • 效果：修复漏洞集合 Fi-，引入新漏洞 Fi+（Fi+ 和 Fi- 无交集）。
• 目标：通过补丁的最短时间序列，使软件无漏洞。补丁可重复使用。

解题思路

1. 状态表示：

   • 用 位掩码（int）表示当前漏洞集合（1 存在，0 不存在）。
   • 初始状态：所有位为 1（(1 << n) - 1）。
   • 目标状态：所有位为 0。

2. BFS 搜索：

   • 队列：存储状态及其累计时间。
   • 补丁检查：对每个状态，检查哪些补丁可应用，生成新状态。
   • 剪枝：记录到达各状态的最短时间，避免重复处理。

3. 补丁处理：

   • 条件检查：用位运算验证 Bi+ 和 Bi-。
   • 状态转移：根据 Fi+ 和 Fi- 更新漏洞集合。

正确代码

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <string>
#include <tr1/unordered_map> // Use tr1 for older compilers

using namespace std;
using namespace std::tr1; // For unordered_map in older compilers

struct State {
    int bugs;
    int time;
    State(int b, int t) : bugs(b), time(t) {}
    bool operator>(const State& other) const {
        return time > other.time;
    }
};

int main() {
    int n, m;
    int case_num = 0;
    while (cin >> n >> m && (n != 0 || m != 0)) {
        case_num++;
        vector<int> times(m);
        vector<int> conditions(m);
        vector<int> effects(m);

        for (int i = 0; i < m; ++i) {
            string cond, eff;
            cin >> times[i] >> cond >> eff;
            int cond_mask = 0;
            int eff_mask = 0;
            for (int j = 0; j < n; ++j) {
                if (cond[j] == '+') cond_mask |= (1 << j);
                else if (cond[j] == '-') cond_mask |= (1 << (j + n));
                if (eff[j] == '+') eff_mask |= (1 << j);
                else if (eff[j] == '-') eff_mask |= (1 << (j + n));
            }
            conditions[i] = cond_mask;
            effects[i] = eff_mask;
        }

        priority_queue<State, vector<State>, greater<State> > pq; // Note the space between '> >'
        unordered_map<int, int> best_time;
        int initial_bugs = (1 << n) - 1;
        pq.push(State(initial_bugs, 0));
        best_time[initial_bugs] = 0;

        int answer = -1;
        while (!pq.empty()) {
            State current = pq.top();
            pq.pop();
            if (current.bugs == 0) {
                answer = current.time;
                break;
            }
            if (current.time > best_time[current.bugs]) continue;
            for (int i = 0; i < m; ++i) {
                if ((current.bugs & conditions[i]) != (conditions[i] & ((1 << n) - 1))) continue;
                if ((~current.bugs & (conditions[i] >> n)) != ((conditions[i] >> n) & ((1 << n) - 1))) continue;
                int new_bugs = (current.bugs & ~(effects[i] >> n)) | (effects[i] & ((1 << n) - 1));
                int new_time = current.time + times[i];
                if (best_time.find(new_bugs) == best_time.end() || new_time < best_time[new_bugs]) {
                    best_time[new_bugs] = new_time;
                    pq.push(State(new_bugs, new_time));
                }
            }
        }

        cout << "Product " << case_num << endl;
        if (answer == -1) {
            cout << "Bugs cannot be fixed." << endl;
        } else {
            cout << "Fastest sequence takes " << answer << " seconds." << endl;
        }
        cout << endl;
    }
    return 0;
}