P2515 [HAOI2010] 软件安装（蓝色提高+/省选-）

SCC + tree DP, https://www.luogu.com.cn/problem/P2515

现在我们的手头有 $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} \neq i)$

输出格式

一个整数，代表最大价值。

输入输出样例 #1

输入 #1

输出 #1

这是一道典型的有向图强连通分量（SCC）缩点与树形背包动态规划结合的题目。

解题思路

关系分析与缩点：
- 每个软件最多依赖另一个软件。如果我们将依赖关系看作有向边（ $D_{i} \to i$ ，表示安装 $i$ 必须先安装 $D_{i}$ ），那么整个图是由若干个基环外向树构成的森林。
- 如果图中存在环（即几个软件相互依赖），由于必须同时安装环中的所有软件，我们可以使用 Tarjan 算法 找出所有的强连通分量（SCC），并将每个 SCC 缩成一个点。
- 缩点后，新点的权重 $W^{'}$ 和价值 $V^{'}$ 分别为原强连通分量中所有点权重之和与价值之和。
重构图为树形结构：
- 缩点后的新图是一个有向无环图（DAG）。因为每个点在原图中最多只有一个入度，所以缩点后的图实际上是一个森林。
- 为了方便进行树形 DP，可以引入一个虚拟根节点 $0$ （其重量和价值均为 $0$ ）。将所有入度为 $0$ 的新节点连接到虚拟根节点 $0$ 下，从而将森林转化为一棵以 $0$ 为根的树。
树形背包 DP：
- 设 $d p [u] [j]$ 表示在以 $u$ 为根的子树中，选择若干节点（必须包含根节点 $u$ ）且总重量不超过 $j$ 时能获得的最大价值。
- 对于每个节点 $u$ ：
  - 若 $j < W_{u}^{'}$ ，由于必须选择 $u$ ，因此状态无效，初始化为 $- 1$ 。
  - 若 $j \geq W_{u}^{'}$ ，初始化 $d p [u] [j] = V_{u}^{'}$ 。
- 然后，递归遍历 $u$ 的每一个子节点 $v$ 并进行背包合并：
  - 对于容量 $j$ 从 $M$ 递减到 $W_{u}^{'}$ ，我们考虑给子树 $v$ 分配容量 $k$ ( $W_{v}^{'} \leq k \leq j - W_{u}^{'}$ )： $d p [u] [j] = max (d p [u] [j], d p [u] [j - k] + d p [v] [k])$ （其中需保证 $d p [v] [k] \neq - 1$ ）。
- 最终，以虚拟根节点 $0$ 运行 DP 后， $d p [0] [M]$ 即为所求的最大价值。

Python 3 实现代码

python

import sys

# 增加递归深度限制，防止树较深时递归溢出
sys.setrecursionlimit(100000)

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    W = [0] + [int(x) for x in input_data[2 : 2 + N]]
    V = [0] + [int(x) for x in input_data[2 + N : 2 + 2 * N]]
    D = [0] + [int(x) for x in input_data[2 + 2 * N : 2 + 3 * N]]
    
    # 1. 构建原图，D[i] -> i 表示安装 i 依赖 D[i]
    adj = [[] for _ in range(N + 1)]
    for i in range(1, N + 1):
        if D[i] != 0:
            adj[D[i]].append(i)
            
    # 2. 使用 Tarjan 算法求强连通分量
    dfn = [0] * (N + 1)
    low = [0] * (N + 1)
    dfn_cnt = 0
    scc = [0] * (N + 1)
    scc_cnt = 0
    stack = []
    in_stack = [False] * (N + 1)
    
    def tarjan(u):
        nonlocal dfn_cnt, scc_cnt
        dfn_cnt += 1
        dfn[u] = low[u] = dfn_cnt
        stack.append(u)
        in_stack[u] = True
        
        for v in adj[u]:
            if not dfn[v]:
                tarjan(v)
                low[u] = min(low[u], low[v])
            elif in_stack[v]:
                low[u] = min(low[u], dfn[v])
                
        if low[u] == dfn[u]:
            scc_cnt += 1
            while True:
                v = stack.pop()
                in_stack[v] = False
                scc[v] = scc_cnt
                if v == u:
                    break
                    
    for i in range(1, N + 1):
        if not dfn[i]:
            tarjan(i)
            
    # 3. 缩点，计算新点的重量和价值
    W_scc = [0] * (scc_cnt + 1)
    V_scc = [0] * (scc_cnt + 1)
    for i in range(1, N + 1):
        W_scc[scc[i]] += W[i]
        V_scc[scc[i]] += V[i]
        
    # 4. 构建缩点后的新图，并统计入度
    adj_scc = [[] for _ in range(scc_cnt + 1)]
    in_degree = [0] * (scc_cnt + 1)
    edges = set()
    
    for u in range(1, N + 1):
        for v in adj[u]:
            su = scc[u]
            sv = scc[v]
            if su != sv and (su, sv) not in edges:
                edges.add((su, sv))
                adj_scc[su].append(sv)
                in_degree[sv] += 1
                
    # 5. 引入虚拟根节点 0，连接所有入度为 0 的节点
    for i in range(1, scc_cnt + 1):
        if in_degree[i] == 0:
            adj_scc[0].append(i)
            
    W_scc[0] = 0
    V_scc[0] = 0
    
    # 6. 树形 DP
    # dp[u][j] 表示在以 u 为根的子树中选择且必须选 u，总重量不超过 j 时的最大价值
    dp = [[-1] * (M + 1) for _ in range(scc_cnt + 1)]
    
    def dfs(u):
        wu = W_scc[u]
        vu = V_scc[u]
        # 初始化选 u 的状态
        for j in range(wu, M + 1):
            dp[u][j] = vu
            
        for v in adj_scc[u]:
            dfs(v)
            wv = W_scc[v]
            # 树形背包合并
            for j in range(M, wu - 1, -1):
                max_val = dp[u][j]
                # 分配给子树 v 的容量为 k
                for k in range(wv, j - wu + 1):
                    val_v = dp[v][k]
                    if val_v != -1:
                        val_u = dp[u][j - k]
                        if val_u + val_v > max_val:
                            max_val = val_u + val_v
                dp[u][j] = max_val

    dfs(0)
    print(dp[0][M])

if __name__ == '__main__':
    solve()

P2515 [HAOI2010] 软件安装（蓝色 提高+/省选-） ​

P2515 [HAOI2010] 软件安装（蓝色提高+/省选-）