57 lines
2.0 KiB
C++
57 lines
2.0 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int N = 310;
|
||
int n, m;
|
||
int w[N];
|
||
int f[N][N];
|
||
//创建邻接表
|
||
int h[N], e[N], ne[N], idx;
|
||
|
||
void add(int a, int b) {
|
||
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
|
||
}
|
||
|
||
//分组背包过程
|
||
void dfs(int u) {
|
||
for (int i = h[u]; i != -1; i = ne[i]) {//物品组
|
||
dfs(e[i]);
|
||
for (int j = m - 1; j >= 0; j--) //体积
|
||
for (int k = 0; k <= j; k++) //决策
|
||
f[u][j] = max(f[u][j], f[u][j - k] + f[e[i]][k]);
|
||
}
|
||
//把老大加上去,同样由于滚动数组对于自己本行的依赖，所以采用了倒序
|
||
//给老大预留了一个位置1,所以i>=1
|
||
for (int i = m; i >= 1; i--) f[u][i] = f[u][i - 1] + w[u];
|
||
//要注意0这个边界，当当前节点的选课数量为0时是没有意义的，所以需要初始化为0，但是其本身就是0，
|
||
//所以这里直接不循环即可,类比一下10_2.cpp
|
||
//f[u][0]=0;
|
||
}
|
||
|
||
int main() {
|
||
/**
|
||
树形DP+01背包-->映射成分组背包
|
||
|
||
如果有三个子树，表示有三个物品组，每个物品组中有m+1(0~m)个物品
|
||
第k个物品的体积是k,价值:f(s1,k)
|
||
|
||
第一层：物品组，第二层：从大到小循环体积，第三层：决策
|
||
时间复杂度：O(n*m^2)
|
||
|
||
但是这道题可能不只有一个点没有父结点，而是有好多点都可能没有父结点，这时，我们可以把0看成虚拟的根结点，最终我们取f[0,m+1]即可
|
||
同时，因为每选一门课，都需要添加上0这个结点，所以最终是m+1
|
||
*/
|
||
cin >> n >> m;
|
||
memset(h, -1, sizeof h);
|
||
for (int i = 1; i <= n; i++) {
|
||
int p;
|
||
cin >> p >> w[i];
|
||
//添加虚拟根的技巧
|
||
add(p, i);//若不存在先修课则该项为0:这为我们创建虚拟根0号结点创造了条件！！！
|
||
}
|
||
//所有方案都需要添加虚拟根结点0，就相当于选了m+1门课
|
||
m++;
|
||
dfs(0);
|
||
cout << f[0][m] << endl;//由于m已经++，所以这里就是f[0][m]了
|
||
return 0;
|
||
} |