Skip to content

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

题解约 1.3 千字
# 洛谷 # LibreOJ # 图论 # 最短路 # 网络流 24 题 # 状态压缩
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

#题面

#题目描述

T 公司发现其研制的一个软件中有 nn 个错误，随即为该软件发放了 mm 个补丁程序。

每一个补丁程序都有其特定的适用环境，某个补丁只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用。一个补丁在排除某些错误的同时，往往会加入另一些错误。

换句话说，对于任意一个补丁 ii，都有四个与之相应的集合 B1i,B2i,F1iB1_i,B2_i,F1_i 和 F2iF2_i。仅当软件包含 B1iB1_i 中的所有错误，而不包含 B2iB2_i 中的任何错误时，才可以使用补丁 ii。补丁 ii 将修复软件中的某些错误集合 F1iF1_i，而同时加入另一些错误 F2iF2_i。另外，运行每个补丁都耗费一定的时间。

试设计一个算法，利用 T 公司提供的 mm 个补丁程序将原软件修复成一个没有错误的软件，并使修复后的软件耗时最少。对于给定的 nn 个错误和 mm 个补丁程序，找到总耗时最少的软件修复方案。

#输入格式

第一行有两个正整数 nn 和 mm。nn 表示错误总数，mm 表示补丁总数。

接下来 mm 行给出了 mm 个补丁的信息。每行包括一个正整数，表示运行补丁程序 ii 所需时间，以及两个长度为 nn 的字符串。中间用一个空格符隔开。

第一个字符串中，如果第 kk 个字符为 +，则表示第 kk 个错误属于 B1iB1_i。若为 -，则表示第 kk 个错误属于 B2iB2_i。若为 0，则第 kk 个错误既不属于 B1iB1_i 也不属于 B2iB2_i，即软件中是否包含第 kk 个错误并不影响补丁 ii 的可用性。

第二个字符串中，如果第 kk 个字符为 -，则表示第 kk 个错误属于 F1iF1_i。若为 +，则表示第 kk 个错误属于 F2iF2_i。若为 0，则第 kk 个错误既不属于 F1iF1_i 也不属于 F2iF2_i，即软件中是否包含第 kk 个错误不会因使用补丁 ii 而改变。

#输出格式

程序运行结束时，将总耗时数输出。如果问题无解，则输出 0。

#输入输出样例

样例输入 #1

3 3
1 000 00-
1 00- 0-+
2 0-- -++

样例输出 #1

8

#数据范围与提示

对于 100%100\% 的数据：1≤n≤201\le n\le 20，1≤m≤1001\le m\le 100。

#思路

状态压缩 + 最短路，不知道为什么这道题也会出现在「网络流 24 题」的题单中。

设状态为 SS，SS 中的第 ii 位表示第 ii 个错误是否存在，那么只需要计算从 2n−12^n - 1 到 00 的最短路即可。

记当前状态为 xx，则能够进行转移的条件为 xx 中包含 B1B1 中的所有错误，并且不包含 B2B2 中的任何错误：

C++
19
20
21
22
23
24
bool check(int s, int i) {
    if ((b1[i] | s) != s) return false;  // 包含 B1 中的所有错误
    if (b2[i] & s) return false;         // 不包含 B2 中的任何错误

    return true;
}

使用了一个补丁之后，需要将 F1F1 中指示的所有位置在状态中设置为 00（u ^ (u & f1[i])），将 F2F2 中指示的所有位置设置为 11（u | f2[i]）。

在 void spfa(int) 中：C++
39
40
41
42
43
44
if (!check(u, i)) continue;

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

if (dist[u] + a[i] < dist[v]) {
    dist[v] = dist[u] + a[i];

开数组的时候不要按照习惯开到 1 << 25，小心 MLE。

#代码

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <algorithm>
#include <array>
#include <queue>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 25,
          M = 105;
const int INF = 0x3f3f3f3f;

int n, m;
std::array<int, M> a, b1, b2, f1, f2;
std::array<int, 1 << N> dist;
std::array<bool, 1 << N> vis;

bool check(int s, int i) {
    if ((b1[i] | s) != s) return false;
    if (b2[i] & s) return false;

    return true;
}

void spfa(int s) {
    std::fill(dist.begin(), dist.end(), INF);

    std::queue<int> q;
    q.push(s);
    dist[s] = 0;
    vis[s] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int i = 1; i <= m; i++) {
            if (!check(u, i)) continue;

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

            if (dist[u] + a[i] < dist[v]) {
                dist[v] = dist[u] + a[i];

                if (!vis[v]) {
                    q.push(v);
                    vis[v] = true;
                }
            }
        }

        vis[u] = false;
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        std::string b, f;

        cin >> a[i] >> b >> f;

        for (int j = 0; j < b.size(); j++) {
            if (b[j] == '+') {
                b1[i] = b1[i] | 1 << j;
            } else if (b[j] == '-') {
                b2[i] = b2[i] | 1 << j;
            }
        }

        for (int j = 0; j < f.size(); j++) {
            if (f[j] == '-') {
                f1[i] = f1[i] | 1 << j;
            } else if (f[j] == '+') {
                f2[i] = f2[i] | 1 << j;
            }
        }
    }

    spfa((1 << n) - 1);

    cout << (dist[0] == INF ? 0 : dist[0]) << endl;

    return 0;
}