[洛谷P2515]软件安装
/ / 阅读耗时 13 分钟难度：省选/NOI-
题目描述
现在我们的手头有$N$个软件，对于一个软件$i$，它要占用$W_i$的磁盘空间，它的价值为$V_i$。我们希望从中选择一些软件安装到一台磁盘容量为$M$计算机上，使得这些软件的价值尽可能大（即$V_i$的和最大）。
但是现在有个问题：软件之间存在依赖关系，即软件i只有在安装了软件$j$（包括软件$j$的直接或间接依赖）的情况下才能正确工作（软件$i$依赖软件$j$)。幸运的是，一个软件最多依赖另外一个软件。如果一个软件不能正常工作，那么它能够发挥的作用为0。
我们现在知道了软件之间的依赖关系：软件i依赖软件$D_i$。现在请你设计出一种方案，安装价值尽量大的软件。一个软件只能被安装一次，如果一个软件没有依赖则$D_i=0$，这时只要这个软件安装了，它就能正常工作。
输入输出格式
输入格式：
第1行：$N,M(0\leq N\leq 100, 0\leq M\leq 500)$
第2行：$W_1,W_2, … W_i, …, W_n (0\leq W_i\leq M)$
第3行：$V_1, V_2, …, V_i, …, V_n (0\leq V_i\leq 1000)$
第4行：$D_1, D_2, …, D_i, …, D_n (0\leq D_i\leq N, D_i≠i)$
输出格式：
一个整数，代表最大价值
输入输出样例
Sample input
3 10
5 5 6
2 3 4
0 1 1
Sample output
5
题解
如果没有依赖问题，这就是一个简单的01背包。软件依赖问题使得本题具有一定难度。
首先根据依赖关系建图，若A依赖于B（B不是0时），那么连一条有向边从B指向A。注意本题中可能出现循环依赖的现象，显然，对于循环依赖的软件，它们要么全被安装，要么全不被安装，因此可以看成一个软件。由于循环依赖的存在，在建完图后，需要用tarjan算法缩点，这样可以得到一个森林。建一个超级源点指向所有树的根结点得到一棵树。
然后就是DP。本人方法比较奇葩：先多叉树转二叉树，然后再DP。规定$dp(i,j)$表示根结点编号为i的子树，空间限制为j时的最大价值，那么显然有：
转移就是向两个子树进行空间分配，取其中的最大值。最终代码如下：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
using namespace std;
int n, m, w[N], v[N], id = 1, dp[N << 2][505], cnt = 1, nw[N << 2], nv[N << 2], degree[N], ch[N << 2][2];
int head[N], color[N], DFN[N], LOW[N], DFNCNT = 1, ID = 1, vis[N], nhead[N], ncnt = 1, in[N << 2];
struct Edge {
int to, next, from;
} edge[N], nedge[N << 1];
inline void add(int x, int y) {
edge[cnt].from = x, edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}
inline void nadd(int x, int y) {
nedge[ncnt].to = y, nedge[ncnt].next = nhead[x], nhead[x] = ncnt++;
}
stack<int> sta;
void tarjan(int x) {//缩点
if (DFN[x])return;
LOW[x] = DFN[x] = DFNCNT++, sta.push(x), vis[x] = 1;
for (int i = head[x]; i; i = edge[i].next) {
if (!DFN[edge[i].to])tarjan(edge[i].to), LOW[x] = min(LOW[x], LOW[edge[i].to]);
else if (vis[edge[i].to])LOW[x] = min(LOW[x], DFN[edge[i].to]);
}
if (DFN[x] == LOW[x]) {
int t;
do color[t = sta.top()] = id, vis[t] = 0, sta.pop();
while (t != x);
++id;
}
}
int DP(int x, int y) {//递归进行DP
if (dp[x][y] != -1)return dp[x][y];
if (y < nw[x])return dp[x][y] = 0;
if (ch[x][0] == 0)return dp[x][y] = nv[x];
if (ch[x][1] == 0)return dp[x][y] = nv[x] + DP(ch[x][0], y - nw[x]);
dp[x][y] = 0;
for (int i = 0; i <= y - nw[x]; i++)
dp[x][y] = max(dp[x][y], DP(ch[x][0], i) + DP(ch[x][1], y - nw[x] - i) + nv[x]);
return dp[x][y];
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++)cin >> w[i];
for (int i = 1; i <= n; i++)cin >> v[i];
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (x != 0)add(x, i);
}
for (int i = 1; i <= n; i++)tarjan(i);
for (int i = 1; i <= n; i++)nw[color[i]] += w[i], nv[color[i]] += v[i];//新建点
for (int i = 1; i < cnt; i++)
if (color[edge[i].from] != color[edge[i].to])
nadd(color[edge[i].from], color[edge[i].to]), ++degree[color[edge[i].from]], ++in[color[edge[i].to]];//重建图
color[0] = id;
for (int i = 1; i < id; i++)if (in[i] == 0)nadd(id, i), ++degree[color[0]];//连接超级源点0
ID = id + 1, memset(dp, -1, sizeof(dp));
for (int i = 1; i <= id; i++) {//多叉树转二叉树
int pt = 0, last = i;
for (int j = nhead[i]; j; j = nedge[j].next) {
if (degree[i] == 1)ch[i][0] = nedge[j].to;
else if (degree[i] == 2)pt ? ch[i][1] = nedge[j].to : ch[i][0] = nedge[j].to, ++pt;
else {
if (pt == degree[i] - 2)ch[last][0] = nedge[j].to, ++pt;
else if (pt == degree[i] - 1)ch[last][1] = nedge[j].to;
else ch[last][0] = nedge[j].to, last = ch[last][1] = ID++, ++pt;
}
}
}
cout << DP(color[0], m);
return 0;
}
这种方法不是正规的，但是是一个很好想的做法，正规解法是树上背包。
同样地，规定$dp(i,j)$为编号为i的子树，限制为j时的最大价值，转移时肯定不能像二叉树那样对子结点分配，只能通过不断更新的方式。1
2
3
4
5
6
7
8
9
10void DP(int x) {
int v;
for (int i = nw[x]; i <= m; i++)dp[x][i] = nv[x];//预处理，其余为0
for (int i = nhead[x]; i; i = nedge[i].next) {//遍历所有结点
DP(v = nedge[i].to);//DP子结点
for (int j = m - nw[x]; j >= 0; j--) {//枚举剩下的空间，倒序枚举
for (int z = 1; z <= j; z++)dp[x][j + nw[x]] = max(dp[x][j + nw[x]], dp[x][j + nw[x] - z] + dp[v][z]);//枚举分配给这个子结点的空间
}
}
}
这样完整代码如下：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
using namespace std;
int n, m, w[N], v[N], id = 1, dp[N << 2][505], cnt = 1, nw[N << 2], nv[N << 2];
int head[N], color[N], DFN[N], LOW[N], DFNCNT = 1, vis[N], nhead[N], ncnt = 1, in[N << 2];
struct Edge {
int to, next, from;
} edge[N], nedge[N << 1];
inline void add(int x, int y) {
edge[cnt].from = x, edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}
inline void nadd(int x, int y) {
nedge[ncnt].to = y, nedge[ncnt].next = nhead[x], nhead[x] = ncnt++;
}
stack<int> sta;
void tarjan(int x) {//缩点
if (DFN[x])return;
LOW[x] = DFN[x] = DFNCNT++, sta.push(x), vis[x] = 1;
for (int i = head[x]; i; i = edge[i].next) {
if (!DFN[edge[i].to])tarjan(edge[i].to), LOW[x] = min(LOW[x], LOW[edge[i].to]);
else if (vis[edge[i].to])LOW[x] = min(LOW[x], DFN[edge[i].to]);
}
if (DFN[x] == LOW[x]) {
int t;
do color[t = sta.top()] = id, vis[t] = 0, sta.pop();
while (t != x);
++id;
}
}
void DP(int x) {
int v;
for (int i = nw[x]; i <= m; i++)dp[x][i] = nv[x];
for (int i = nhead[x]; i; i = nedge[i].next) {
DP(v = nedge[i].to);
for (int j = m - nw[x]; j >= 0; j--) {
for (int z = 1; z <= j; z++)dp[x][j + nw[x]] = max(dp[x][j + nw[x]], dp[x][j + nw[x] - z] + dp[v][z]);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++)cin >> w[i];
for (int i = 1; i <= n; i++)cin >> v[i];
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
if (x != 0)add(x, i);
}
for (int i = 1; i <= n; i++)tarjan(i);
for (int i = 1; i <= n; i++)nw[color[i]] += w[i], nv[color[i]] += v[i];//新建点
for (int i = 1; i < cnt; i++)
if (color[edge[i].from] != color[edge[i].to])
nadd(color[edge[i].from], color[edge[i].to]), ++in[color[edge[i].to]];//重建图
color[0] = id;
for (int i = 1; i < id; i++)if (in[i] == 0)nadd(id, i);
DP(color[0]);
cout << dp[color[0]][m];
return 0;
}