ural 1018 Binary Apple Tree

浏览数：23 / 时间：2015年06月11日

1018. Binary Apple Tree

Time limit: 1.0 second
Memory limit: 64 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 integers 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:

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 (2 ≤ N ≤ 100; 1 ≤ Q ≤ N ? 1). 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 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

刚开始学树状dp，欢迎来喷。

有一颗苹果树，它的树枝符合完全二叉树。每个树枝上有一些苹果。节点标号为1~N(1为根节点)。现在因为树枝太多了，需要保留q根树枝。问最多能保留多少苹果。

题目给出的数据并没有按照跟节点到子节点的顺序给出，如何建树便一直困扰了我好久(战五渣-。-)。最终借助结构体存放两个儿子的下标比较优美地建出来了。

接下来讲转移。显然我们不光要考虑节点，还要考虑以该节点为根的树选择了多少条边。

dp[t][k] : 已 t 为根的子树保留k条边(树枝)最多能保留多少条苹果。

由此我们可以发现如果在某个节点保留了k条边，有以下两种情况。

　　1：只选择一棵子树。那么dp[t][k] = max(dp[t.l][k-1] + w[t][t.l], dp[t.r][k-1] + w[t][t.r]) //意思是在该子树(左或右)选择k-1条边，并加上根节点到该子树的边。

　　2：选择两颗子树。那么就存在两条固定的边(根节点到其左右孩子的边)，dp[t][k] = w[t][t.l] +w[t][t.r] + max(dp[t.l][j] + dp[t.r][k - j - 2]) /*(j : 0 ~ K-2)*/ 。

　　即左子树和右子树总共选择k-2条边。

由此，输出dp[1][q]就好。

#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

struct Node {
    int l, r;
}T[105];

int n, q;
int dp[105][105], map[105][105];

void buildTree(int t) {//建树
    int flag = 0; 
    for (int i=0; i<=n; i++) {
        if (map[t][i] && !T[i].l && !T[t].r) {//!T[i].l不为父节点
            if (!T[t].l) T[t].l = i;
            else T[t].r = i;
            flag = 1;
        }
    }
    if (flag) {
        buildTree(T[t].l);
        buildTree(T[t].r);
    }
}

void Tdp (int s) {
    if (T[s].l == 0) return ;
    Tdp(T[s].l);
    Tdp(T[s].r);
    for (int i=1; i<=q; i++) {//转移
        dp[s][i] = max(dp[T[s].l][i-1] + map[s][T[s].l], dp[T[s].r][i-1] + map[s][T[s].r]);
        for (int j=0; j<i-1; j++) {
            dp[s][i] = max(dp[s][i], dp[T[s].l][j] + dp[T[s].r][i-j-2] + map[s][T[s].l] + map[s][T[s].r]);
        }
    }
}

int main () {
    cin >> n >> q ;
    int a, b, c;
    for (int i=1; i<n; i++) {
        cin >> a >> b >> c;
        map[a][b] = map[b][a] = c;
    }
    buildTree(1);
    Tdp(1);
    cout << dp[1][q] <<endl;
    return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

ural 1018 Binary Apple Tree