[网络流24题]P2761 软件补丁
DP
https://www.luogu.com.cn/problem/P2761
这道题其实是个很显然的DP吧，理论复杂度 \(O(2^{20}m)\)， 都1e8了，虽然这个跑不满但是还是挺哈人的，哦对这题还是1s
点击查看代码
#include
using namespace std;
struct pack {
int f1, f2, b1, b2, t;
} p[505];
int n, m, s, minn[(1 << 20 )+ 5], tag;
bool dp[(1 << 20) + 5];
inline int gtag();
void spfa() {
memset(minn, 0x3f, sizeof(minn));
queue q;
minn[s] = 0;
q.push(s);
while (!q.empty()) {
int x = q.front();
for (int i = 1; i <= m; ++i)
if ((x & p[i].b1) == p[i].b1 && (x & p[i].b2) == 0) {
int y = ((x | p[i].f1) | p[i].f2) ^ p[i].f1;
if (minn[x] + p[i].t < minn[y]) {
minn[y] = minn[x] + p[i].t;
if (!dp[y]) {
q.push(y);
dp[y] = true;
}
}
}
dp[x] = false;
q.pop();
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
cin >> p[i].t;
for (int j = 1; j <= n; ++j) {
tag = gtag();
if (tag == 1) p[i].b1 |= (1 << j - 1);
if (tag == 2) p[i].b2 |= (1 << j - 1);
}
for (int j = 1; j <= n; ++j) {
tag = gtag();
if (tag == 1) p[i].f2 |= (1 << j - 1);
if (tag == 2) p[i].f1 |= (1 << j - 1);
}
}
s = (1 << n) - 1;
spfa();
if (minn[0] == 0x3f3f3f3f)
cout << 0;
else
cout << minn[0];
return 0;
}
inline int gtag() {
char ch = getchar();
while (ch != '+' && ch != '-' && ch != '0') ch = getchar();
if (ch == '+') return 1;
if (ch == '-') return 2;
return 0;
}