UVa 1407 树形背包 Caves

这道题可以和POJ 2486 树形背包DP Apple Tree比较着来做。

参考题解

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 using namespace std;

 const int maxn =  + ;

 int n, Q;

 vector<int> G[maxn], C[maxn];

 int d[maxn][maxn][], cnt[maxn];

 void dfs(int u)

 {

     cnt[u] = ;

     d[u][][] = d[u][][] = ;

     for(int i = ; i < G[u].size(); i++)

     {

         int v = G[u][i];

         int w = C[u][i];

         dfs(v);

         cnt[u] += cnt[v];

         for(int j = cnt[u]; j >= ; j--)

             for(int x = ; x <= j && x <= cnt[v]; x++)

             {

                 d[u][j][] = min(d[u][j][], d[v][x][] + d[u][j-x][] + w * );

                 d[u][j][] = min(d[u][j][], d[v][x][] + d[u][j-x][] + w * );

                 d[u][j][] = min(d[u][j][], d[v][x][] + d[u][j-x][] + w);

             }

     }

 }

 int main()

 {

     int kase = ;

     while(scanf("%d", &n) ==  && n)

     {

         for(int i = ; i < n; i++) { G[i].clear(); C[i].clear(); }

         for(int i = ; i < n; i++)

         {

             int a, b, d; scanf("%d%d%d", &a, &b, &d);

             G[b].push_back(a); C[b].push_back(d);

         }

         memset(d, 0x3f, sizeof(d));

         dfs();

         printf("Case %d:\n", kase++);

         scanf("%d", &Q);

         while(Q--)

         {

             int x; scanf("%d", &x);

             int ans;

             for(ans = n; ans > ; ans--) if(d[][ans][] <= x) break;

             printf("%d\n", ans);

         }

     }

     return ;

 }

代码君