ZOJ 3201 树形背包问题

题目大意：

0~n-1号这n个点，每个点有个权值，由无向边形成了一棵树，希望在这棵树上找到一棵长为m的子树使总的权值最小

基本的树形背包问题

令dp[u][j] 表示u号节点对应子树中有j个节点所能得到的最大权值

dp[u][1] = val[u]

dp[u][j] = max{dp[v][k] + dp[u][j-k]} j>1 1=<k<j

我们通过dfs自底向上更新

在dfs过程中建立一个 j ，k 的循环即可

我一开始想的时候认为这个只做到了 u 的下方考虑，如果所得到的子树是要往u的上方走怎么办，想着自顶向上多一次dfs，然后就再也想不出来了- -

其实后来想想却发现如果要往上走，那么就得到的是以走到最上方的那个节点所形成的子树，那个值也已经在dp数组中保存了，不用我多去考虑了

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 using namespace std;

 const int N = ;

 int first[N] , k , val[N] , dp[N][N];

 struct Edge{

     int y , next;

 }e[N<<];

 void add_edge(int x , int y)

 {

     e[k].y = y , e[k].next = first[x];

     first[x] = k++;

 }

 void  dfs(int u , int fa , int m)

 {

     dp[u][] = val[u];

     for(int i = first[u] ; i!=- ; i=e[i].next)

     {

         int v = e[i].y;

         if(v == fa) continue;

         dfs(v , u , m);

         for(int j = m ; j>= ; j--){

             for(int k= ; k<j ; k++)

                 dp[u][j] = max(dp[u][j] , dp[v][k] + dp[u][j-k]);

         }

     }

 }

 int main()

 {

    // freopen("a.in" , "r" , stdin);

     int n , m , x , y;

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

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

             scanf("%d" , val+i);

         memset(first , - , sizeof(first));

         k=;

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

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

             add_edge(x , y);

             add_edge(y , x);

         }

         memset(dp ,  , sizeof(dp));

         dfs( , - , m);

         int maxn = ;

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

             maxn = max(maxn , dp[i][m]);

         }

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

     }

     return ;

 }

巴特西

ZOJ 3201 树形背包问题

最新文章

热门文章