随笔 - 87  文章 - 279  trackbacks - 0
<2024年11月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

潜心看书研究!

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 214327
  • 排名 - 116

最新评论

阅读排行榜

评论排行榜

1018. A Binary Apple Tree
Time Limit: 1.0 second
Memory Limit: 16 MB

Let's imagine how apple tree looks in binary computer world. You're right, it looks just like a binary tree, i.e. any biparous branch splits up to exactly two new branches. We will enumerate by natural numbers the root of binary apple tree, points of branching and the ends of twigs. This way we may distinguish different branches by their ending points. We will assume that root of tree always is numbered by 1 and all numbers used for enumerating are numbered in range from 1 to N, where N is the total number of all enumerated points. For instance in the picture below N is equal to 5. Here is an example of an enumerated tree with four branches:

   2   5
\ /
3   4
\ /
1
As you may know it's not convenient to pick an apples from a tree when there are too much of branches. That's why some of them should be removed from a tree. But you are interested in removing branches in the way of minimal loss of apples. So your are given amounts of apples on a branches and amount of branches that should be preserved. Your task is to determine how many apples can remain on a tree after removing of excessive branches.

 

Input

First line of input contains two numbers: N and Q (1 ≤ QN, 1 < N ≤ 100). N denotes the number of enumerated points in a tree. Q denotes amount of branches that should be preserved. Next N-1 lines contains descriptions of branches. Each description consists of a three integer numbers divided by spaces. The first two of them define branch by it's ending points. The third number defines the number of apples on this branch. You may assume that no branch contains more than 30000 apples.

Output

Output file should contain the only number — amount of apples that can be preserved. And don't forget to preserve tree's root ;-)

Sample

input
output
5 2
            1 3 1
            1 4 10
            2 3 20
            3 5 20
            
21
            

Problem Source: Ural State University Internal Contest '99 #2
#include <iostream>
using namespace std;

const int MAXN = 110;
const int MAXQ = 110;

int n, q;
int d[MAXN][MAXQ];
int g[MAXN][MAXN], deg[MAXN], nw[MAXN], son[MAXN][2];
int root;
int f[MAXN], isleaf[MAXN];

inline 
int maxt(int a, int b) {
    
return a > b ? a : b;
}


void DFS(int v) {
    
int i, t = 0;
    
for (i=1; i<=n; i++{
        
if (g[v][i] != -1 && !f[i]) {
            son[v][t
++= i;
            f[i] 
= 1;
            nw[i] 
= g[v][i];
            DFS(i);
        }

    }

    
if (!t) isleaf[v] = 1;
}


void buildT() {
    
int i;
    
for (i=1; i<=n; i++{
        
if (deg[i] == 2{
            root 
= i;
            
break;
        }

    }

    f[root] 
= 1; nw[root] = 0;
    DFS(root);
}


int DP(int ti, int tl) {
    
if (tl <= 0return 0;
    
if (d[ti][tl] != -1return d[ti][tl];
    
if (isleaf[ti]) return nw[ti];
    
int k, tmp = 0;
    
for (k=0; k<tl; k++{
        tmp 
= maxt(tmp, DP(son[ti][0], k)+DP(son[ti][1], tl-1-k));
    }

    d[ti][tl] 
= tmp + nw[ti];
    
return d[ti][tl];
}


int main() {
    
int i, j, k, x, y, w;
    scanf(
"%d%d"&n, &q);
    memset(g, 
-1sizeof(g));
    memset(d, 
-1sizeof(d));
    
for (i=0; i<n-1; i++{
        scanf(
"%d%d%d"&x, &y, &w); 
        g[x][y] 
= g[y][x] = w;
        deg[x]
++, deg[y]++;
    }

    buildT();
    printf(
"%d\n", DP(root, q+1));

    
return 0;
}

posted on 2007-04-20 20:05 阅读(1551) 评论(2)  编辑 收藏 引用 所属分类: ACM题目

FeedBack:
# re: ural 1018(简单的树状dp) 2007-09-26 21:49 zYc
Thank you!  回复  更多评论
  
# re: ural 1018(简单的树状dp) 2008-02-25 21:24 jkdjfkdjfkdjflasdkjfkjeijfkdsjfkd
弱弱的膜拜一下  回复  更多评论
  

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