原题链接

考察:树形背包dp

本来不想写这篇的题解,因为和前面的题重复了...但是WA了3次才对,还是写一下吧..

思路:

        将每20个虫子看成财宝的一个体积.m是背包的体积.这就是带体积的树形背包问题了.但是要注意的是,当某个洞穴虫子=0,我们还需要派人去拿.这个处理很简单,让f[u][0]=0就可以了.其实际意义是:在u的子树中,当当前背包体积=0,获得财富==0.

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cstring>
 5 using namespace std;
 6 const int N = 110;
 7 int h[N],idx,w[N],n,m,bug[N];
 8 int f[N][N];
 9 struct Road{
10     int to,ne;
11 }road[N<<1];
12 void add(int a,int b)
13 {
14     road[idx].to = b,road[idx].ne = h[a],h[a] = idx++; 
15 }
16 void inits()
17 {
18     memset(h,-1,sizeof h); idx = 0;
19     memset(f,0,sizeof f);
20 }
21 void dfs(int u,int fa)
22 {
23     for(int i=h[u];i!=-1;i=road[i].ne)
24     {
25         int v = road[i].to;
26         if(v==fa) continue;
27         dfs(v,u);
28         for(int j=m-bug[u];j>=0;j--)
29           for(int k=0;k<=j;k++)
30             f[u][j] = max(f[u][j-k]+f[v][k],f[u][j]);
31     }
32     for(int i=m;i>=bug[u];i--) f[u][i] = f[u][i-bug[u]]+w[u];
33     for(int i=0;i<bug[u];i++) f[u][i] = 0;
34     f[u][0] = 0;
35 }
36 int main()
37 {
38     while(scanf("%d%d",&n,&m)!=EOF&&n!=-1)
39     {
40         inits();
41         for(int i=1;i<=n;i++) scanf("%d%d",&bug[i],&w[i]);
42         for(int i=1;i<=n;i++) bug[i] = (bug[i]+19)/20;
43         for(int i=1;i<n;i++)
44         {
45             int x,y;
46             scanf("%d%d",&x,&y);
47             add(x,y); add(y,x);
48         }
49         dfs(1,-1);
50         printf("%d\n",f[1][m]);
51     }
52     return 0;
53 }