洛谷P2761《软件补丁问题》

或 CTSC99《补丁 VS 错误》

说的那么麻烦,其实就一最短路。。

题目传送门:https://www.luogu.com.cn/problem/P2761

解析

第一个,这题是状压,反正错误不超过 20 个;

第二个,这题要在一个一个状态之间转移,因为补丁包修复错误的同时还带来了错误;

第三个,这题有起始状态(全是错误)和最终状态(没有错误),状态转移还有额外代价。

所以!这题用动态规划最短路肯定没错!


把 20 个错误的拥有情况压成 20 位的 int,0 表示无此错误,1 表示有此错误

把这些状态抽象成点,在一个一个状态之间转移的补丁包抽象成有向边,补丁包的安装时间抽象成边权,跑最短路就完了


问题是,边的数量未免有点太多了吧,可以构造出一个全 0 的补丁包,这样所有的点都要连边啊 qaq

那就索性不连边了……反正就 100 个补丁包,每次 for 一遍检查哪些补丁包能用的也没大问题


检查补丁包能不能用这个我不用再讲了吧……基本二进制操作

有一个小 trick:在修复软件包的时候不能直接把错误状态和修复状态异或(因为有些错误可能并不存在,这时候异或就不对了),例子是 1011 ^ 0111 = 1100 != 1000。这时候可以先让它强制获得这个错误,然后再修复掉这些错误,也就是先 1011 | 01111111 ^ 0111

代码实现

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
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <queue>

const int MAXM = 100 + 10;
const int MAX_NODE = (1 << 22);

int n, m;

struct Patch {
int usage;
int required, requiredNot;
int fixedBugs, newBugs;

Patch(int _us = 0, int _r = 0, int _rn = 0, int _f = 0, int _n = 0) : usage(_us), required(_r), requiredNot(_rn), fixedBugs(_f), newBugs(_n) {}
void read() {
std::string requireStr, effectStr;
std::cin >> usage >> requireStr >> effectStr;
for (int i = 0; i < n; ++i) {
if (requireStr[i] == '+') required += (1 << (i));
else if (requireStr[i] == '-') requiredNot += (1 << (i));
if (effectStr[i] == '-') fixedBugs += (1 << (i));
else if (effectStr[i] == '+') newBugs += (1 << (i));
}
}
} patches[MAXM];

struct Node {
int id, wt;
Node(int _i = 0, int _w = 0) : id(_i), wt(_w) {}
bool operator < (const Node &that) const {
return wt > that.wt;
}
};

int dist[MAX_NODE];
bool vis[MAX_NODE];

int getInstallResult(int id, Patch p) {
if ((id | p.required) != id) return -1;
if ((id & p.requiredNot) != 0) return -1;
int res = (((id | p.fixedBugs) ^ p.fixedBugs) | p.newBugs);
return res;
}

void shortestPath() {
std::priority_queue<Node> q;
int init = ((1 << n) - 1);
while (!q.empty()) q.pop();
q.push(Node(init, 0));
memset(dist, 0x3f, sizeof dist);
dist[init] = 0;
while (!q.empty()) {
Node nownode = q.top(); q.pop();
int u = nownode.id;
if (vis[u]) continue; vis[u] = true;
for (int i = 1; i <= m; ++i) {
int res = getInstallResult(u, patches[i]);
if (res == -1) continue;
if (dist[res] > dist[u] + patches[i].usage) {
dist[res] = dist[u] + patches[i].usage;
q.push(Node(res, dist[res]));
}
}
}
}

int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; ++i) {
patches[i].read();
}
shortestPath();
if (dist[0] != 0x3f3f3f3f) printf("%d\n", dist[0]);
else puts("0");
return 0;
}