AcWing 10. 有依赖的背包问题
原题链接
困难
作者:
妙WA草
,
2022-07-04 15:10:52
,
所有人可见
,
阅读 219
题目描述
AcWing 10. 有依赖的背包问题
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 110;
int n,m,root,head[N],k = 1,v[N],w[N],f[110][110];
/*
集合:第u个结点及他下面结点使用j体积空间的价值的集合
属性:MAX
*/
struct node//结点
{
int to,next;
}e[N];
void add(int f,int s)//建边
{
e[k].to = s;
e[k].next = head[f];
head[f] = k ++;
}
void dfs(int u)
{
//对于u这个结点,当给它的体积大于v[u]时,最小价值等于本身
for(int i = v[u]; i <= m; i ++)f[u][i] = w[u];
for(int i = head[u]; ~ i; i = e[i].next)//遍历子节点
{
int t = e[i].to;//子节点的编号
dfs(t);//搜子节点
for(int j = m; j >= v[u]; j --)//对于u结点,当使用体积为j时求最大价值
{
for(int k = 1; k <= j - v[u]; k ++)//对于u结点的这个子节点,给他体积k,看给他
{ //的k体积和自身的j-k体积能否创造出更大价值
f[u][j] = max(f[u][j],f[t][k] + f[u][j - k]);
}
}
}
}
int main()
{
memset(head,-1,sizeof head);//初始化head数组
cin >> n >> m;
for(int i = 1; i <= n ; i ++)//建图
{
int f;
cin >> v[i] >> w[i] >> f;
if(f == -1)root = i;//找根节点
else add(f,i);
}
dfs(root);
cout << f[root][m] << endl;
return 0;
}