[HAOI2010] 软件安装

形式化题目

给定 $N$ 个软件，每个软件占用空间 $W_i$ ，能产生的价值为 $V_i$ 。计算机磁盘总容量为 $M$ 。每个软件 $i$ 最多依赖一个前置软件 $D_i$ ：

若 $D_i = 0$ ，表示该软件无依赖，安装后即可发挥价值；
若 $D_i \neq 0$ ，表示必须在软件 $D_i$ 及其全部直接或间接依赖均被安装的情况下，软件 $i$ 才能发挥价值。

求在总占用空间不超过 $M$ 的前提下，安装的软件能获得的最大总价值。

暴力解法

思路

每个软件有安装和不安装两种选择。可以枚举所有 $2^N$ 种子集状态：

用二进制状态掩码枚举每个软件是否被选中；
对选中的软件集合，检查其依赖闭包是否合法：若选中了软件 $i$ 且 $D_i \neq 0$ ，则 $D_i$ 必须也已被选中；
若合法且所选软件的总体积不超过 $M$ ，计算所选软件的总价值并更新全局最优解。

代码

cpp

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-23 23:30
 * update_at: 2026-10-23 23:30
 */
// brute.cpp：小数据指数级枚举暴力解
// 枚举全部 2^N 种选择方案，逐一检查前置依赖是否全部满足且总空间不超过 M
// 时间复杂度 O(2^N * N)，仅适用于 N <= 20 的小规模数据对拍与验证
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 105;

ll n, m;
ll w[MAXN], v[MAXN], d[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> m)) return 0;
    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) cin >> d[i];

    ll ans = 0;
    int limit = 1 << n;
    for (int mask = 0; mask < limit; ++mask) {
        bool ok = true;
        ll total_w = 0;
        ll total_v = 0;

        for (int i = 1; i <= n; ++i) {
            if ((mask >> (i - 1)) & 1) {
                total_w += w[i];
                total_v += v[i];
                if (d[i] != 0) {
                    if (!((mask >> (d[i] - 1)) & 1)) {
                        ok = false;
                        break;
                    }
                }
            }
        }

        if (ok && total_w <= m) {
            if (total_v > ans) {
                ans = total_v;
            }
        }
    }

    cout << ans << "\n";
    return 0;
}

复杂度

时间复杂度： $O(2^N \cdot N)$ 。外层枚举所有 $2^N$ 种选择子集，内层遍历 $N$ 个软件验证依赖合法性并统计体积与价值。
空间复杂度： $O(N)$ 。仅需存储每个软件的重量、价值和前置依赖数组。

瓶颈

当 $N \le 100$ 时， $2^{100}$ 远远超出运算承受能力。暴力枚举没有利用依赖关系的图结构特征：同一个环上的软件必须整体绑定，树状分支上的选择具有分组背包的最优子结构。

正解

思路

1. 强连通分量与缩点

将依赖关系抽象为有向图：

若软件 $i$ 依赖于 $D_i$ ( $D_i \neq 0$ )，建立一条有向边 $D_i \to i$ （表示“必须先装 $D_i$ ，才能装 $i$ ”）。
如果依赖关系出现环（例如 $A \to B \to C \to A$ ），由于选其中任何一个都需要前置已被安装，推导可得：环上的所有软件要么全部安装，要么都不安装。
因此，使用 Tarjan 算法求出图中所有的强连通分量（SCC），将每个 SCC 缩为一个“超点”：
- 超点空间 $W'_{scc} = \sum_{u \in scc} W_u$ ；
- 超点价值 $V'_{scc} = \sum_{u \in scc} V_u$ 。

2. 重建树形结构与虚拟根

缩点后原图转化为了有向无环图（DAG）：

在缩点后的新图里，每个超点最多只有一条入边（因为原图中每个点最多只有一个前置依赖）。
为了处理无依赖的节点以及孤立的闭合依赖环，建立一个虚拟根节点 $0$ （其空间为 $0$ ，价值为 $0$ ）。
统计所有 SCC 的入度，将所有入度为 $0$ 的 SCC 均连接到虚拟根 $0$ 的后继（即 $0 \to scc$ ）。
此时，整张图变成以 $0$ 为根节点的树形依赖结构（选子节点必须先选父节点）。

3. 树上背包 DP

在建立的树上进行树形分组背包 DP（同经典模型 P2014 选课）：

设 $dp[u][j]$ 表示在以 $u$ 为根的子树中选择，花费容量不超过 $j$ 所能获得的最大总价值。
初始化：选 $u$ 的子树必须先选 $u$ 本身，因此当容量 $j \ge W'_u$ 时， $dp[u][j] = V'_u$ ，其余为 $0$ 。
转移：遍历 $u$ 的每个子节点 $v$ ，先递归计算子树 $v$ 的 DP 值，再采用分组背包思想倒序更新 $u$ 的容量：
$dp[u][j] = \max_{0 \le k \le j - W'_u} \{ dp[u][j - k] + dp[v][k] \}$
其中外层倒序枚举 $j \in [M, W'_u]$ ，内层枚举分配给子节点 $v$ 的容量 $k \in [0, j - W'_u]$ 。
最终答案：从虚拟根 $0$ 开始 DFS，结果为 $dp[0][M]$ 。

代码

cpp

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
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-23 23:30
 * update_at: 2026-10-23 23:30
 */
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long ll;

const int MAXN = 105;
const int MAXM = 505;

ll n, m;
ll w[MAXN], v[MAXN], d[MAXN];

// 原图邻接表（d[i] -> i，表示选了 d[i] 才能选 i）
int head[MAXN], to_e[MAXN], nxt[MAXN], edge_cnt;

void add_edge(int u, int to) {
    edge_cnt++;
    to_e[edge_cnt] = to;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// Tarjan 相关
int dfn[MAXN], low[MAXN], timer;
int stk[MAXN], top;
bool in_stack[MAXN];
int scc_id[MAXN], scc_cnt;
ll scc_w[MAXN], scc_v[MAXN];

void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    stk[++top] = u;
    in_stack[u] = true;

    for (int e = head[u]; e; e = nxt[e]) {
        int v_node = to_e[e];
        if (!dfn[v_node]) {
            tarjan(v_node);
            low[u] = min(low[u], low[v_node]);
        } else if (in_stack[v_node]) {
            low[u] = min(low[u], dfn[v_node]);
        }
    }

    if (low[u] == dfn[u]) {
        scc_cnt++;
        while (true) {
            int cur = stk[top--];
            in_stack[cur] = false;
            scc_id[cur] = scc_cnt;
            scc_w[scc_cnt] += w[cur];
            scc_v[scc_cnt] += v[cur];
            if (cur == u) break;
        }
    }
}

// 缩点后新图的树边（从父亲到儿子）
int head_tree[MAXN], to_tree[MAXN * MAXN], nxt_tree[MAXN * MAXN], tree_edge_cnt;
int in_deg[MAXN];
bool has_edge[MAXN][MAXN];

void add_tree_edge(int u, int to) {
    tree_edge_cnt++;
    to_tree[tree_edge_cnt] = to;
    nxt_tree[tree_edge_cnt] = head_tree[u];
    head_tree[u] = tree_edge_cnt;
}

// 树上背包 DP
// dp[u][j] 表示在以 u 为根的子树中选择，占用容量不超过 j 获得的最大价值
ll dp[MAXN][MAXM];

void dfs_dp(int u) {
    // 必须选 u 才能选其子树
    for (int j = scc_w[u]; j <= m; ++j) {
        dp[u][j] = scc_v[u];
    }

    for (int e = head_tree[u]; e; e = nxt_tree[e]) {
        int to = to_tree[e];
        dfs_dp(to);

        // 分组背包：倒序枚举背包容量，防止重复使用子树
        for (int j = m; j >= scc_w[u]; --j) {
            for (int k = 0; k <= j - scc_w[u]; ++k) {
                dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[to][k]);
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;
    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) {
        cin >> d[i];
        if (d[i] != 0) {
            // 建原图依赖边：i 依赖 d[i]，即 d[i] -> i，表示前置为 d[i]
            // 为了找强连通分量，有向环在 d[i] -> i 或 i -> d[i] 下是等价的（只是环的方向反转）
            add_edge(d[i], i);
        }
    }

    // 1. Tarjan 缩点求强连通分量
    for (int i = 1; i <= n; ++i) {
        if (!dfn[i]) {
            tarjan(i);
        }
    }

    // 2. 建立缩点后的 DAG，并接入虚拟根 0
    for (int i = 1; i <= n; ++i) {
        if (d[i] != 0) {
            int u_scc = scc_id[d[i]];
            int v_scc = scc_id[i];
            if (u_scc != v_scc && !has_edge[u_scc][v_scc]) {
                has_edge[u_scc][v_scc] = true;
                add_tree_edge(u_scc, v_scc);
                in_deg[v_scc]++;
            }
        }
    }

    // 入度为 0 的 SCC 挂在虚拟根 0 下（包括孤立环与依赖 0 的点）
    for (int i = 1; i <= scc_cnt; ++i) {
        if (in_deg[i] == 0) {
            add_tree_edge(0, i);
        }
    }

    // 虚拟根 0 本身体积 0，价值 0
    scc_w[0] = 0;
    scc_v[0] = 0;

    // 3. 树上背包 DP
    dfs_dp(0);

    cout << dp[0][m] << "\n";

    return 0;
}

复杂度

时间复杂度： $O(N + M^2 \cdot N')$ 。
- Tarjan 算法和新图构建阶段点数和边数均为 $O(N)$ ，耗时 $O(N)$ ；
- 树上分组背包中，节点数 $N' \le N + 1$ 。树上每个节点合并子树时，容量枚举上限为 $M$ ，总运算次数为 $O(N' \cdot M^2)$ 。当 $N \le 100, M \le 500$ 时， $100 \times 500^2 \approx 2.5 \times 10^7$ 次计算，可在 1 秒时限内轻松通过。
空间复杂度： $O(N \cdot M)$ 。链式前向星和 Tarjan 辅助数组空间为 $O(N)$ ，DP 数组状态数为 $(N + 1) \times (M + 1)$ ，总内存占用小于 1 MB。

总结

本题的关键在于利用依赖关系的单前置约束识别出基环森林结构，通过 Tarjan 缩点将相互循环依赖的软件分量打包为不可分割的整体物品，从而将图简化为有向树；再借助超级虚拟根将森林统一为单一单根树，最终套用树上背包 DP 求解。