洛谷P2761《软件补丁问题》

一月 17, 2020 2935

或 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 | 0111 再 1111 ^ 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
81
#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;
}