P2761 软件补丁问题

P2761 软件补丁问题

思路

貌似不用网络流，直接状态压缩

用spfa跑最短路，直接判断是否能过

位运算太渣了，WA了好几发

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 21, M = 101, inf = 0x3f3f3f3f;

int read() {

    int x = 0, f = 1; char s = getchar();

    for(; s > '9' || s < '0'; s = getchar()) if(s == '-') f = -1;

    for(; s >= '0' && s <= '9'; s = getchar()) x = x * 10 + s - '0';

    return x * f;

}

int n, m, tim[M], dis[1<<N], b1[M], b2[M], f1[M], f2[M];

bool vis[1<<N];

char s[N];

void spfa() {

    memset(dis, 0x3f, sizeof(dis));

    dis[(1<<n)-1] = 0;

    queue<int> q;

    q.push((1<<n)-1);

    while(!q.empty()) {

        int u = q.front();

        q.pop();

        vis[u] = 0;

        for(int i = 1; i <= m; ++i) {

            int v = (u & (~f1[i])) | f2[i];

            if(dis[v] > dis[u] + tim[i]) {

                if((u & b2[i]) == 0 && ((u | b1[i]) == u)) {

                    dis[v] = dis[u] + tim[i];

                    if(!vis[v]) {

                        vis[v] = 1;

                        q.push(v);

                    }

                }

            }

        }

    }

}

int main() {

    n = read(), m = read();

    for(int i = 1; i <= m; ++i) {

        tim[i] = read();

        scanf("%s", s);

        for(int j = 0; j < n; ++j) {

            if(s[j] == '+') b1[i] |= (1<<j);

            else if(s[j] == '-') b2[i] |= (1<<j);

        }

        scanf("%s", s);

        for(int j = 0; j < n; ++j) {

            if(s[j] == '-') f1[i] |= (1<<j);

            else if(s[j] == '+') f2[i] |= (1<<j);

        }

    }

    spfa();

    if(dis[0] == inf) dis[0] = 0;

    printf("%d\n", dis[0]);

    return 0;

}