树形依赖背包（codevs1155 金明的预算方案 2006年NOIP全国联赛提高组）

http://codevs.cn/problem/1155/

dfs自然的生成依赖关系

然后搜索前update

搜索后dp转移一下

为了方便，令root=0

将森林构建成树

具体看代码

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
using namespace std;
inline void read(int &ans){
ans=0;char x=getchar();int f=1;
while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
while(x>='0'&&x<='9')ans=ans*10+x-'0',x=getchar();
ans*=f;
}
const int MAXN=60+10;
const int MAXM=30000+10;
struct node{int v,next;}E[MAXN<<1];
int head[MAXN<<1],tot,val[MAXN],cost[MAXN],n,m,ans,F[MAXN][MAXM];
void add(int u,int v){E[++tot]=(node){v,head[u]},head[u]=tot;}
void dfs(int u,int fa,int M){
if(M>0)
for(int i=head[u];~i;i=E[i].next){
int v=E[i].v;
if(v!=fa){
for(int j=0;j<=m-cost[v];++j)
F[v][j]=F[u][j]+cost[v]*val[v];
dfs(v,u,m-cost[v]);
for(int j=cost[v];j<=m;++j)
F[u][j]=max(F[u][j],F[v][j-cost[v]]);
}
}
}
int v;
int main(){
read(m),read(n);
memset(head,-1,sizeof(head));
for(int i=1;i<=n;i++)
read(cost[i]),read(val[i]),read(v),add(i,v),add(v,i);
dfs(0,0,m);
printf("%dn",F[0][m]);
return 0;
}

最后

以上就是无心香水为你收集整理的树形依赖背包（codevs1155 金明的预算方案 2006年NOIP全国联赛提高组）的全部内容，希望文章能够帮你解决树形依赖背包（codevs1155 金明的预算方案 2006年NOIP全国联赛提高组）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。