gzwzm06

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  1 随笔 :: 52 文章 :: 17 评论 :: 0 Trackbacks

求最大权值的子树

dp[root][i] = MAX{dp[root][j] + dp[child][i – j]}

其中 K >= i >= 2

表示以root为根,节点数为i 的子树的最大权值

 1#include <cstdio>
 2
 3const int SIZE = 101;
 4
 5struct TREE
 6{
 7    int m_arr[SIZE];
 8    int m_size;
 9    int m_value;
10}
tree[SIZE];
11
12int N, K;
13int dp[SIZE][SIZE];
14
15inline int MAX(const int& a, const int& b)
16{
17    return (a > b ? a : b);
18}

19
20void Init()
21{
22    int i;
23    for ( i = 0; i < SIZE; ++i )
24        tree[i].m_size = 0;
25}

26
27void DFS( const int& root, const int& fat )
28{
29    int i, j, k;
30
31    dp[root][0= 0;
32    dp[root][1= tree[root].m_value;
33    for ( i = 2; i <= K; ++i )
34        dp[root][i] = -1;
35
36    for ( i = 0; i < tree[root].m_size; ++i )
37    {
38        int x = tree[root].m_arr[i];
39
40        if ( x == fat )
41            continue;
42
43        DFS( x, root );
44
45        for ( j = K; j >= 2--j )
46        {
47            int t = -1;
48            for ( k = 1; k <= j; ++k )
49            {
50                if ( dp[root][k] == -1 || dp[x][j - k] == -1 )
51                    continue;
52                t = MAX( t, dp[root][k] + dp[x][j - k] );
53            }

54            dp[root][j] = t;
55        }

56    }

57}

58
59void Solve()
60{
61    int ans = 0;
62
63    DFS( 0-1 );
64
65    for ( int i = 0; i < N; ++i )
66        if ( ans < dp[i][K] )
67            ans = dp[i][K];
68
69    printf("%d\n", ans);
70}

71
72int main()
73{
74    //freopen("1.txt", "r", stdin);
75
76    int i, x, y;
77
78    while ( scanf("%d %d"&N, &K) != EOF )
79    {
80        Init();
81
82        for ( i = 0; i < N; ++i )
83            scanf("%d"&tree[i].m_value);
84
85        for ( i = 0; i < N - 1++i )
86        {
87            scanf("%d %d"&x, &y);
88            tree[x].m_arr[tree[x].m_size++= y;
89            tree[y].m_arr[tree[y].m_size++= x;
90        }

91
92        Solve();
93    }

94
95    return 0;
96}
posted on 2009-05-05 09:39 阅读(301) 评论(0)  编辑 收藏 引用 所属分类: DP

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理