update\ on\ 2025.4.30
代码中有一处错误，修正一下，要将f数组的初值赋为极大值，否则可能会导致结果错误

软件安装 题解

题面

传送门

N个物品，背包体积为V，每个物品有价值v_{i}以及体积w_{i}，每个物品至多有一个依赖物品（选每个物品前必须先选它的依赖物品）d_{i}，若d_{i}为0，则没有依赖物品，可以直接选择。

求体积限制为V的情况下最大价值

0\leq N\leq 100,\,0\leq w_{i}\leq M \leq 500
0\leq v_{i} \leq 1000,\,0\leq d_{i}\leq N,\,d_{i}\neq i

题解

思路

这个题有些棘手的是每个物品都有一个依赖物品，我们没办法随便选，那怎么办呢？

仔细观察这种依赖关系，可以发现，这种依赖关系很像一种树形结构，有了父节点，才能有子节点。事实上，我们可以通过树形结构来解决这道题。

但是现在我们面前又出现了一个问题，就是题中所给的数据并不是树形结构，而是一个可能有环的图。我们想把它转化成树形结构，方便我们进行树上DP，将图中相互依赖的强连通分量缩点，然后再用一个0节点作树根，把一个森林变成树，从而进行树上DP

树上DP
设计dp状态f[x][i]表示在x这棵子树上体积限制为i所能获得的最大价值。

那么如何转移呢

1. 先枚举儿子，递归求解儿子的f数组
2. 枚举当前节点及其子树的体积限制
3. 枚举当前儿子及其子树的体积限制

注意，这里相当于把每个儿子看作很多个物品，从这些物品中选择一个最优的来更新父节点当前枚举i容量下的f数组，所以我们当成分组背包来进行遍历求解。

写成伪代码

时间复杂度O(nm^{2})，下方会有一个优化版本的dfs，O(nm)，不过对于这题来说O(nm^{2})也够用了

具体实现中注意一些细节即可AC此题

code

const int N = 110;
int n, m;
int h[N], ver[N], ne[N], tot;
int v[N], w[N], d[N], f[N][510], siz[N];
int vv[N], ww[N];
int dfn[N], low[N], st[N], tim, top, in[N];;
int bel[N], cnt;
bool ins[N];
vector <int> e[N];

void add(int x, int y) {
	ver[++tot] = y;
	ne[tot] = h[x];
	h[x] = tot;
}

void tarjan (int x) {
	dfn[x] = low[x] = ++tim;
	st[++top] = x;
	ins[x] = 1;
	
	for (int i = h[x]; i; i = ne[i]) {
		int y = ver[i];
		if (!dfn[y]) {
			tarjan(y);
			low[x] = min(low[x], low[y]); 
		} else if (ins[y]) {
			low[x] = min(low[x], dfn[y]);
		}
	}
	if (low[x] == dfn[x]) {
		cnt++;
		while (st[top] != x) {
			bel[st[top]] = cnt;
			ins[st[top]] = 0;
			vv[cnt] += v[st[top]];
			ww[cnt] += w[st[top]];
			top--;
		}
		bel[st[top]] = cnt;
		ins[st[top]] = 0;
		vv[cnt] += v[st[top]];
		ww[cnt] += w[st[top]];
		top--;
	}
}

void dfs (int x) {
	//这里的初始化一定要加，否则会错
	for (int i = 0; i <= m; i++) {
		f[x][i] = -1e9;
	}
	f[x][ww[x]] = vv[x];
	for (int i = 0; i < (int)e[x].size(); i++) {
		int y = e[x][i];
		dfs(y);
		for (int j = m; j >= ww[x]; j--) {
			for (int k = 0; k <= j - ww[x]; k++) {
				f[x][j] = max(f[x][j], f[x][j - k] + f[y][k]);
			}
		}
	}
}
int main () {
	scanf("%d%d", &n, &m);
	
	for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
	for (int i = 1; i <= n; i++) scanf("%d", &v[i]);
	
	for (int i = 1; i <= n; i++) {
		scanf("%d", &d[i]);
		if(d[i] == 0) continue;
		add(d[i], i);
	}
	for (int i = 1; i <= n; i++) {
		if (!dfn[i]) tarjan(i);
	}
	for (int i = 1; i <= n; i++) {
		if (d[i] == 0) continue;
		if (bel[d[i]] != bel[i]) {
			e[bel[d[i]]].push_back((bel[i]));
			in[bel[i]]++;
		}
	}
	for (int i = 1; i <= cnt; i++) {
		if (in[i] == 0) {
			e[0].push_back(i);
		}
	}
	dfs(0);
	
	int ans = 0;
	for (int i = 0; i <= m; i++) {
		ans = max(ans, f[0][i]);
	}
	printf("%d\n", ans);
	
	return 0;
}

优化版本dfs

void dfs(int x) {
	//这里的初始化一定要加，否则会错
	for (int i = 0; i <= m; i++) {
		f[x][i] = -1e9;
	}
	siz[x] = w[x];
	f[x][w[x]] = v[x];
	for(int i = h[x]; i; i = ne[i]) {
		int y = ver[i];
		dfs(y);
		for(int j = min(siz[x] + siz[y], m); j >= w[x]; j--) {
			//这两种形式等价
			for(int k = max(j - siz[x], 0); k <= min(j - w[x], siz[y]); k++) {
				f[x][j] = max(f[x][j], f[x][j - k] + f[y][k]);
			}
			for(int k = max(j - siz[y], w[x]); k <= min(siz[x], j - 1); k++) {
				f[x][j] = max(f[x][j], f[x][k] + f[y][j - k]);
			}
		}
		siz[x] += siz[y];
	}
}