AcWing 10. 有依赖的背包问题
原题链接
困难
作者:
HUE_ACM
,
2021-12-16 21:14:08
,
所有人可见
,
阅读 176
const int N = 110;
int idx, e[N], ne[N], h[N];
int n, V, v[N], w[N], root, fa;
int f[N][N];
void add(int a, int b) {
e[++idx] = b; ne[idx] = h[a]; h[a] = idx;
}
void dfs(int fa) {
for(int i = h[fa]; i; i = ne[i]) {
int son = e[i];
dfs(son);
/*
* j : 父节点使用了多少容量
* k : 子节点使用了多少容量
* 分组背包问题 :
* 在这里 k 不同代表:同一组内不同的方案,即一个节点,只能选择它每个 son 的一种状态 (son 的状态有 -> f[son][0~V])
* 这里假设先不选 父节点u 所以子节点占用父节点的体积(fa 给 son 留的体积)只能是 j -> [0 ~ V - v[fa]]
* f[son][k] : son的其中一种状态(son为根的子树使用了 k 的体积的 max ),而儿子使用的体积不能超过 fa 给 son 留的体积(j) ( k <= j )
* 所以状态转移 : f[fa][j] = max(f[fa][j], f[fa][j - k] + f[son][k])
* 描述 : fa 留给 son 体积 j 的空间(且当前 fa 不参与状态的) 与
* fa 留给 son 体积 (j - k) 的空间(且当前 fa 不参与状态的) + son 使用 体积 k 的空间的 max
* 补充 : 这里使用的 f[fa][j - k] 的状态也需要是最优的,故 k 的循环方式为正序循环
*/
for(int j = V - v[fa]; j >= 0; j--) {
for(int k = 0; k <= j; k++) {
f[fa][j] = max(f[fa][j], f[fa][j - k] + f[son][k]);
}
}
}
/*
* 考虑 fa 节点对状态产生的影响
* 当 fa 为根节点的子树使用了超过 v[fa] 的体积时, f[fa][j : (j >= v[fa])]
* = 不考虑 fa 节点下 以 fa 为根的子树使用了 体积 (j - v[fa]) + fa 节点的贡献
*
* 当 fa 为根节点的子树使用了小于 v[fa] 的体积时, f[fa][j : (j < v[fa])]
* = 0 : fa 节点无法放入,所以 以 fa 为根节点的子树上所有的点都无法放入
*/
for(int i = V; i >= v[fa]; i--) f[fa][i] = f[fa][i - v[fa]] + w[fa];
for(int i = 0; i < v[fa]; i++) f[fa][i] = 0;
}
int main (void) {
scanf("%d%d", &n, &V);
for(int i = 1; i <= n; i++) {
scanf("%d%d%d", &v[i], &w[i], &fa);
if(fa == -1) root = i;
else {
add(fa, i);
}
}
dfs(root);
printf("%d", f[root][V]);
return 0;
}