翻车笔记_ 软件补丁问题 [最短路, 状压, 翻车]

Merry Christmas :.☆(~▽~)/$:°★

coding还是很暖心的嘛…虽然我不过圣诞节…

懵逼的 题目

最近刷网络流24题…啥都不会…
除了二分图的板子就剩这个题了…
…这tm是网络流???

传送至 Luogu

扯淡的 题解

因为数据服务很小…把有哪些位置有bug压成一个整形, 作为一个状态, 也就是图中的一个点, 补丁看做边, 然后跑最短路就行…..了吗?
因为点最多到(1 << 20)…所以边其实是存不下来的…随机存边失败后…看题解里说…可以每次转移的时候枚举每一条边…emmmmmm….

注意几个问题…好像题解是错的

1
2
3
(x & y) // 如果x中和y中有至少一个重合的元素, 返回true
(x & (~y)) // 如果y中的元素x中一个也没有, 返回true
((x & y) == y) // 如果x包含y中所有的元素, 返回true

沙茶的 代码

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
#define MAXN ((1 << 20) + 5)
#define MAXM (100 + 5)
#define MAXn (20 + 5)
#define INF (0x7ffffff)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define pii pair<int, int>
using namespace std;
struct edg
{
int cnth;
int msth;
int mbug;
int lbug;
int cost;
edg() {}
edg(int c, int m, int mo, int l, int co): cnth(c), msth(m), mbug(mo), lbug(l), cost(co) {}
} b[MAXM];
bool inq[MAXN];

struct cmp
{
bool operator () (const pii x, const pii y)
{
return x.second > y.second;
}
};

int n;
int km;
int s, t = 0;
int ans = 0;
int dis[MAXN];
void init();
void spfa(int);
inline bool pd(int, int);
int main()
{
init();
// dijk(s);
spfa(s);
if (ans < INF)
printf("%d", ans);
else
puts("0");
return 0;
}
void init()
{
scanf("%d%d", &n, &km);
s = (1 << n) - 1;
char sx[MAXn], sy[MAXn];
int cnth, msth, mbug, lbug;
int src;
for (int i = 1; i <= km; i++)
{
scanf("%d", &src);
scanf("%s%s", sx, sy);
cnth = msth = mbug = lbug = 0;
for (int j = 0; j < n; j++)
{
cnth <<= 1, msth <<= 1, mbug <<= 1, lbug <<= 1;
if (sx[j] == '+')
{
msth |= 1;
}
else if (sx[j] == '-')
{
cnth |= 1;
}
if (sy[j] == '-')
{
lbug |= 1;
}
else if (sy[j] == '+')
{
mbug |= 1;
}
}
b[i] = edg(cnth, msth, mbug, lbug, src);
}
}

void spfa(int start)
{
memset(inq, false, sizeof(inq));
memset(dis, 0x7f, sizeof(dis));
queue<int> q;
q.push(start);
dis[start] = 0;
inq[start] = true;
while (!q.empty())
{
int dq = q.front();
q.pop();
inq[dq] = false;
for (int i = 1; i <= km; i++)
{
if (pd(dq, i))
{
int bt = ((dq & (~(b[i].lbug))) | b[i].mbug);
if (dis[bt] > dis[dq] + b[i].cost)
{
dis[bt] = dis[dq] + b[i].cost;
if (!inq[bt])
{
q.push(bt);
inq[bt] = true;
}
}
}

}
}
ans = dis[t];
}
inline bool pd(int dq, int i)
{
if ((dq & b[i].msth) != b[i].msth)
return false;
if (dq & b[i].cnth)
return false;
return true;
}

/*
2 4
1 +- --
0 -0 0+
1 0+ 0-
0 +- 00
*/

By 啥都不会的 Cansult