依赖背包(树形背包)。见代码：
#include<iostream>
#include<vector>
using namespace std;
int N,M;
int val[205];
int vis[205];
int f[205][205];
int dp[205][205];
vector<int> tree[205];
int max(int a,int b)
{
return a>b?a:b;
}
void dfs(int x)
{
int i,j,k;
vis[x]=1;
dp[x][0]=0;
f[x][0]=0;
for(i=0;i<tree[x].size();i++)
for(j=M;j>=0;j--)
{
int temp=tree[x][i];
if(!vis[temp]) dfs(temp);
for(k=0;k<=M;k++)
{
if(dp[temp][k]!=-1&&j>=k&&f[x][j-k]!=-1)
f[x][j]=max(f[x][j],f[x][j-k]+dp[temp][k]);
}
}
for(i=1;i<=M+1;i++)
if(f[x][i-1]!=-1) dp[x][i]=f[x][i-1]+val[x];
}
int main()
{
while(scanf("%d%d",&N,&M)!=EOF&&(N||M))
{
int i,a,b;
for(i=0;i<=N;i++)
tree[i].clear();
for(i=1;i<=N;i++)
{
scanf("%d%d",&a,&b);
tree[a].push_back(i);
val[i]=b;
}
val[0]=0;
memset(vis,0,sizeof(vis));
memset(dp,-1,sizeof(dp));
memset(f,-1,sizeof(f));
dfs(0);
printf("%d\n",dp[0][M+1]);
}
return 0;
}
posted on 2010-08-05 18:00
wuxu 阅读(943)
评论(4) 编辑 收藏 引用 所属分类:
动态规划