「网络流24题」软件补丁问题-题解

题目传送门: 「Luogu P2761」软件补丁问题

题目大意

$n$个错误,$m$个补丁

第$i$个补丁耗时$t_i$
使用该补丁需要软件中包含所有$B1_i$中的错误,并且不包含$B2_i$中的任何一个错误
该补丁可以修复错误$F1_i$,但会添加错误$F2_i$

找出修复所有错误的最短时间

题解

错误较少,可以使用状态压缩,用2进制表示错误的修复情况(1表示未修复,0表示已修复)
起始状态$\texttt{111…1}$,结束状态$\texttt{000…0}$

每个状态当做图中的节点,即求起始状态到结束状态的最短路

由于补丁较少,不用连边,在最短路需要遍历边时,遍历所有补丁,并判断是否能够联通(即当前状态是否包含该补丁的$B1$,而不包含$B2$)
如果能够连接,则下一个状态为当前状态打上当前补丁(即修复$F1$,添加$F2$)
边权为当前补丁的耗时
使用SPFA跑最短路即可

代码

#include <bits/stdc++.h>
using namespace std;

inline int read() {
    int x = 0; int f = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch))  {x = x * 10 + ch - 48; ch = getchar();}
    return x * f;
}

inline int read_() {
    char ch = getchar();
    while (ch != '+' && ch != '-' && ch != '0') ch = getchar();
    if (ch == '+') return 1;
    else if (ch == '-') return 2;
    return 0;
}

const int inf = 0x3f3f3f3f;

struct DLL {
    int time;
    int b1, b2;
    int f1, f2;
}node[110];

int n, m, s, t;
int dis[1 << 21];
bool vis[1 << 21];

void SPFA(int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0; vis[s] = true;
    queue<int> q; q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        vis[u] = false;
        for (int i = 1; i <= m; ++i) {
            if ((u & node[i].b1) == node[i].b1 && (u & node[i].b2) == 0) {
                int v = ((u | node[i].f1) | node[i].f2) ^ node[i].f1;
                if (dis[v] > dis[u] + node[i].time) {
                    dis[v] = dis[u] + node[i].time;
                    if (!vis[v]) {
                        q.push(v);
                        vis[v] = true;
                    }
                }
            }
        }
    }
}

int main() {
    n = read(); m = read();
    s = (1 << n) - 1; t = 0;
    for (int i = 1; i <= m; ++i) {
        node[i].time = read();
        for (int j = 0; j < n; ++j) {
            int sta = read_();
            if (sta == 1) node[i].b1 |= (1 << j);
            if (sta == 2) node[i].b2 |= (1 << j);
        }
        for (int j = 0; j < n; ++j) {
            int sta = read_();
            if (sta == 2) node[i].f1 |= (1 << j);
            if (sta == 1) node[i].f2 |= (1 << j);
        }
    }
    SPFA(s);
    printf("%d\n", dis[t] == inf ? 0 : dis[t]);
    return 0;
}