ZOJ 3201 Tree of Tree（樹形DP）

轉載請注明出處：憶夢http://blog.csdn.net/yimeng2013/article/details/10274993

題目連結：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3201

題目大意：先給出N，K，N代表有N個結點，K代表選擇K個結點大小的子樹，求出最大權值

題解：典型的樹形dp，用dp[i][j]:表示以i為根，有j個節點（切樹根必須選，是以dp[i][1] = val[i]）,選了該子樹中j個節點時候的最大權值。       因為最多選m個，那麼這m個中去枚舉這個孩子哄占多少個，樹根占多少個      dp[root][j] = max( dp[root][j] , dp[root][k] + dp[u][j-k] );   

存儲結構用的是鍊式前向星，A了 寫了一個vector版  但不知道為嘛一直WA，以後再補上來

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;

#define N 105
struct Edge
{
    int vert , next;
}e[N * 2];

int dp[N][N];
int head[N];
int val[N];
int vis[N];
int n,m;

void DFS( int root )
{

    int i , j , k , u;

     dp[root][1] = val[root];
    
    for(i=head[root];  i != -1;  i=e[i].next)
    {
         u = e[i].vert;
         if( vis[u] )  
			 continue;
         vis[u]++;

         DFS(u);
         
         for( j=m;  j>=1;  j--)
             for(k=1;  k<=j;  k++)
                 dp[root][j] = max( dp[root][j] , dp[root][k] + dp[u][j-k] );
    }
    
}

void init()
{
	int u, v;
	int num = 1;
	for(int i=1;  i<n;  i++)
      {
         scanf("%d%d" , &u , &v );   
         e[num].vert = v;
         e[num].next = head[u];
         head[u] = num++;
            
         e[num].vert = u;
         e[num].next = head[v];
         head[v] = num++;    
        
       }
}
int main()
{
    int i , j;
    
    while( scanf("%d%d" , &n , &m ) != EOF )
    {
        for(i=0;  i<n;  i++  )
            scanf("%d" , &val[i] );
        
        memset(head , -1 , sizeof(head) );
        memset(vis , 0 , sizeof(vis) );
        memset(dp , 0,  sizeof(dp) );
        
	    init();
        
        vis[0]++;
        DFS(0);
        
		int ans = 0;
        for(i = 0;  i<n;  i++  )
            if( ans < dp[i][m] )
                 ans = dp[i][m] ;

         
         printf("%d\n" , ans );
        
    }
    return 0;
}