网络流24题 软件补丁问题

题目传送门

好久之前做的+2，现在才写博客……
填一下网络流24题的坑

---

状压集合\(B1,B2\)，对于一个补丁\(i\)，向\(B1_i\)和\(B2_i\)之间连一条边权为所需时间的单向边
然后跑最短路就好了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define LL long long
using namespace std;
struct zzz {
    int len, b1, b2, f1, f2;
}node[110];
LL read() {
    LL k = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9')
      k = k * 10 + c - 48, c = getchar();
    return k * f;
}
int dis[1 << 21], vis[1 << 21], n, m;
void SPFA(int s) {
    queue <int> q; q.push(s);
    memset(dis, 127, sizeof(dis)); dis[s] = 0; vis[s] = 1;
    while(!q.empty()) {
        int k = q.front(); q.pop(); vis[k] = 0;
        for(int i = 1; i <= m; ++i) {
            zzz &a = node[i];
            if(a.b2 & k || (a.b1 & k) < a.b1) continue;
            int x = ((k ^ (k & a.f1)) | a.f2);
            if(dis[x] > dis[k] + a.len) {
                dis[x] = dis[k] + a.len;
                if(!vis[x]) {
                    vis[x] = 1; q.push(x);
                }
            }
        }
    }
}
int main() {
    n = read(), m = read();
    for(int i = 1; i <= m; ++i) {
        int t = read();
        char c1[30], c2[30]; cin >> c1 >> c2;
        int b1 = 0, b2 = 0, f1 = 0, f2 = 0;
        for(int i = 0; i <= n-1; ++i) {
            if(c1[i] == '+') b1 += (1 << i);
            if(c1[i] == '-') b2 += (1 << i);
        }
        for(int i = 0; i <= n-1; ++i) {
            if(c2[i] == '-') f1 += (1 << i);
            if(c2[i] == '+') f2 += (1 << i);
        }
        node[i] = (zzz){t, b1, b2, f1, f2};
    }
    SPFA((1 << n) - 1);
    if(dis[0] > 214748364) cout << 0;
    else cout << dis[0];
    return 0;
}