[BZOJ 2427][HAOI 2010]软件安装

题目大意

\(n\) 个软件,对于软件 \(i\),它要占用 \(W_i\) 的磁盘空间,价值为 \(V_i\) 。从中选择一些软件安装到一台磁盘容量为 \(M\) 的 计算机上,使得这些软件的价值尽可能大。软件之间存在依赖关系,即软件 \(i\) 只有在安装了软件 \(j\)(包括直接或间接依赖)的情况下才能发挥价值,一个软件最多依赖另外一个软件。

\(1 \leqslant n \leqslant 100\)

\(0 \leqslant W_i \leqslant m \leqslant 500\)

\(0 \leqslant V_i \leqslant 1,000\)

题目链接

BZOJ 2427

题解

Tarjan 缩圈 + 树形 DP + 背包 DP。

依赖关系会有环,环上的软件要么同时选,要么同时不选,缩成的点的软件大小、价值均为和。

对于依赖关系 \(i\) 依赖 \(j\) ,从 \(j\)\(i\) 连边。把某节点的所有子节点当物品进行背包 DP(物品大小要枚举一下)。

代码

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
#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>
const int MAXN = 105;
const int MAXM = 505;
template <typename T>
struct Edge {
T *u, *v;
Edge() {}
Edge(T *u, T *v) : u(u), v(v) {}
};
struct Conn {
std::vector<Edge<Conn> > e;
int w, v, deg, f[MAXM];
} C[MAXN];
int sccCnt;
void addEdge(Conn *u, Conn *v) {
u->e.push_back(Edge<Conn>(u, v));
v->deg++;
}
struct Node {
std::vector<Edge<Node> > e;
Conn *conn;
int w, v, dfn, low;
bool ins;
} N[MAXN];
void addEdge(int u, int v) {
N[u].e.push_back(Edge<Node>(&N[u], &N[v]));
}
namespace Tarjan {
std::stack<Node *> s;
int dfsClock;
void dfs(Node *u) {
s.push(u);
u->ins = true;
u->dfn = u->low = ++dfsClock;
for (std::vector<Edge<Node> >::iterator e = u->e.begin(); e != u->e.end(); e++) {
if (!e->v->dfn) {
dfs(e->v);
u->low = std::min(u->low, e->v->low);
} else if (e->v->ins) u->low = std::min(u->low, e->v->dfn);
}
if (u->dfn == u->low) {
sccCnt++;
Node *v;
do {
v = s.top();
s.pop();
v->ins = false;
v->conn = &C[sccCnt];
C[sccCnt].w += v->w;
C[sccCnt].v += v->v;
} while (u != v);
}
}
void findSCC(int n) {
dfsClock = 0;
while (!s.empty()) s.pop();
for (int i = 1; i <= n; i++) if (!N[i].dfn) dfs(&N[i]);
}
}
void rebuild(int n) {
for (int i = 1; i <= n; i++) for (std::vector<Edge<Node> >::iterator e = N[i].e.begin(); e != N[i].e.end(); e++)
if (e->u->conn != e->v->conn) addEdge(e->u->conn, e->v->conn);
for (int i = 1; i <= sccCnt; i++) if (!C[i].deg) addEdge(&C[0], &C[i]);
}
int m;
void dfs(Conn *u) {
for (int i = u->w; i <= m; i++) u->f[i] = u->v;
for (std::vector<Edge<Conn> >::iterator e = u->e.begin(); e != u->e.end(); e++) {
dfs(e->v);
for (int j = m; j >= u->w; j--) for (int k = 0; k <= j - u->w; k++)
u->f[j] = std::max(u->f[j], u->f[j - k] + e->v->f[k]);
}
}
int main() {
int n;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &N[i].w);
for (int i = 1; i <= n; i++) scanf("%d", &N[i].v);
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
if (x) addEdge(x, i);
}
Tarjan::findSCC(n);
rebuild(n);
dfs(&C[0]);
int ans = 0;
for (int i = 0; i <= m; i++) ans = std::max(ans, C[0].f[i]);
printf("%d\n", ans);
return 0;
}