11076: 【原1076】小F的苹果树

题目描述

author: 寿鹤鸣原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1076

Description

小F有一颗苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）

这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。

我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树

2 5

现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。

给定需要保留的树枝数量，求出最多能留住多少苹果。

Input Format

第1行2个数，N和Q(\(1 \leq Q \leq N\),1 < N < 101)。

N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。

每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。

每根树枝上的苹果不超过30000个。第1行2个数，N和Q(\(1 \leq Q \leq N\),1 < N < 101)。

N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。

每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。

每根树枝上的苹果不超过30000个。

Output Format

一个数，最多能留住的苹果的数量。

Hint

Sample Input

Sample Output

FineArtz's solution

/* 小F的苹果树 */
#include <iostream>
#include <set>
using namespace std;

class Node{
public:
    set<int> edge;
    int father = 0;
    int apple = 0, sumApple = 0, sum = 0;
};

class Edge{
public:
    int u = 0, v = 0, w = 0;
};

Node a[105];
Edge e[105];
int n, q;
int f[105][105] = {0};

void buildTree(int x, int f){
    a[x].father = f;
    for (int i : a[x].edge){
        if (i != f)
            buildTree(i, x);
    }
}

void countApple(int x){
    a[x].sumApple = a[x].apple;
    a[x].sum = 1;
    for (int i : a[x].edge){
        if (i != a[x].father){
            countApple(i);
            a[x].sumApple += a[i].sumApple;
            a[x].sum += a[i].sum;
        }
    }
}

int dp(int x, int m){
    if (f[x][m] != 0)
        return f[x][m];
    if (m == 0){
        f[x][m] = 0;
        return 0;
    }
    if (m >= a[x].sum){
        f[x][m] = a[x].sumApple;
        return f[x][m];
    }
    if (a[x].edge.size() == 1){
        f[x][m] = a[x].apple;
        return f[x][m];
    }
    int s1 = 0, s2 = 0;
    for (int i : a[x].edge){
        if (i != a[x].father){
            if (s1 == 0)
                s1 = i;
            else
                s2 = i;
        }
    }
    for (int k = 0; k < m; ++k){
        f[x][m] = max(f[x][m], dp(s1, k) + dp(s2, m - k - 1) + a[x].apple);
    }
    return f[x][m];
}

void print(int x){
    cout << x << ' ' << a[x].father << ' ' << a[x].apple << ' ' << a[x].sumApple << ' ' << a[x].sum << endl;
    for (int i : a[x].edge)
        if (i != a[x].father)
            print(i);
}

int main(){
    cin >> n >> q;
    for (int i = 1; i < n; ++i){
        cin >> e[i].u >> e[i].v >> e[i].w;
        a[e[i].u].edge.insert(e[i].v);
        a[e[i].v].edge.insert(e[i].u);
    }
    buildTree(1, 0);
    for (int i = 1; i < n; ++i){
        if (a[e[i].u].father == e[i].v)
            a[e[i].u].apple = e[i].w;
        else
            a[e[i].v].apple = e[i].w;
    }
    countApple(1);
    //print(1);
    ++q;
    dp(1, q);
    cout << f[1][q] << endl;
    return 0;
}

yyong119's solution

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

const int MAX_N = 110;
struct Node{
    int lc, rc;
    int val;
};
Node tree[MAX_N];
int m, n;
int arr[MAX_N][MAX_N];
int f[MAX_N][MAX_N];
bool vis[MAX_N];

void Create(int root) {

    vis[root] = true;
    for (int i = 1; i <= m; ++i) {
        if (!vis[i] && arr[root][i]) {
            if (!tree[root].lc) tree[root].lc = i;
            else tree[root].rc = i;
            tree[i].val = arr[root][i];
            Create(i);
        }
    }
}

int TreeDP(int root, int e) {

    if (root == 0 || e == 0) return 0;
    if (f[root][e]) return f[root][e];
    int maxx = 0, l, r;
    for (int i = 0; i < e; ++i) {
        l = TreeDP(tree[root].lc, i);
        r = TreeDP(tree[root].rc, e - i - 1);
        maxx = max(l + r, maxx);
    }
    f[root][e] = maxx + tree[root].val;
    return f[root][e];
}

int main() {

    ios::sync_with_stdio(false);
    cin >> m >> n;
    int from, to, value;
    for (int i = 1; i < m; ++i) {
        cin >> from >> to >> value;
        arr[to][from] = arr[from][to] = value;
    }
    Create(1);
    cout << TreeDP(1, ++n) << endl;
    return 0;
}