本文共 2153 字，大约阅读时间需要 7 分钟。

#洛谷P2761、vijos P1019、codevs1239、codevs2218#

题目大意

有n个错误，m个不同的补丁。每个补丁都有两个描述字符串：“+”和“-”。使用一个补丁的条件是当前的错误集合必须包含“+”字符串中所有的错误，但不包含“-”字符串中的任何错误。使用该补丁后，会修复“-”字符串中的所有错误，同时新增“+”字符串中的错误。每个补丁使用一次需要一定的时间，问最短需要多少时间才能修复所有错误。如果无法完成，输出0。

解题思路

代码实现

#include 
   
    
#include 
    
     
#include 
     
      
int n, m;
int dis[1 << 21];
bool vis[1 << 21];
struct Buding {
    int t;
    int has, donthas, ac, wa;
    Buding(int t = 0) : has(0), donthas(0), ac(0), wa(0) {}
    Buding(int t, int h, int d, int a, int w) : has(h), donthas(d), ac(a), wa(w), t(t) {}
};
Buding e[m + 1];
char b[30], f[30];
std::queue
      
        q;
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        scanf("%d %s %s", &e[i].t, b, f);
        e[i].has = 0;
        e[i].donthas = 0;
        for (int j = 0; j < n; ++j) {
            if (b[j] == '-') e[i].donthas |= 1 << j;
            if (f[j] == '-') e[i].ac |= 1 << j;
        }
    }
    int initial = (1 << n) - 1;
    dis[initial] = 0;
    vis[initial] = true;
    q.push(initial);
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (dis[u] != dis[u]) continue;
        for (int i = 1; i <= m; ++i) {
            Buding &p = e[i];
            if ((u & p.has) == p.has && (u & p.donthas) == 0) {
                int to = (p.wa | (~p.ac)) | p.has;
                if (dis[u] + p.t < dis[to]) {
                    dis[to] = dis[u] + p.t;
                    if (!vis[to]) {
                        vis[to] = true;
                        q.push(to);
                    }
                }
            }
        }
    }
    if (dis[0] == 0x3f3f3f3f) puts("0");
    else puts(dis[0]);
    return 0;
}
      
     
    
   

代码解释