洛谷

洛谷题单指南-树与图上的动态规划-P2015 二叉苹果树

原题链接：https://www.luogu.com.cn/problem/P2015

题意解读：一棵树，边有权值，求从树中选择不超过q条边的最大权值和。

解题思路：

一、三维解法：

利用分组背包的思想，将一个节点的所有子树看做一组物品，枚举背包体积，再枚举某一组中所有的物品

1、状态表示

设f[i][j][k]表示以i为根的子树中在前j个子树中选总树枝数量不超过k时的最大苹果数
2、状态转移

设根节点u，对于u的每一个子节点v，有递推关系

枚举u的所有子树v (对应分组背包的一个分组)

  枚举从树中可以选的最大边数k：0~q （对应背包的体积）

    枚举可以从子树v中选择的边数s：0~k-1，最多是k-1因为u->v的边要单独算 （对应一组中的一种物品）

f[u][j][k] = f[u][j - 1][k]; //不选v这棵子树
for(int s = 0; s < k; s++) //选v这棵子树
{
    f[u][j][k] = max(f[u][j][k], f[v][cnt[v]][s] + f[u][j - 1][k - s - 1] + w[i]);
}

3、初始化：f[x][0][x] = 0

4、结果：f[1][cnt[1]][q]

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 105, M = 205;
int head[N], to[M], w[M], nxt[M], idx;
int cnt[N]; //cnt[i]表示i有多少个子节点
int f[N][N][N]; //f[i][j][k]表示以i为根的子树中在前j个子树中选总树枝数量不超过k时的最大苹果数
int n, q;

void add(int a, int b, int c)
{
    to[++idx] = b;
    w[idx] = c;
    nxt[idx] = head[a];
    head[a] = idx;
}

void dfs(int u, int p)
{
    int j = 0;
    for(int i = head[u]; i; i = nxt[i])
    {
        int v = to[i];
        if(v == p) continue;

        dfs(v, u);
        j++; //子节点数量加1
        cnt[u]++; //记录u的子节点数量

        for(int k = 0; k <= q; k++)
        {
            f[u][j][k] = f[u][j - 1][k]; //不选v这棵子树
            for(int s = 0; s < k; s++) //选v这棵子树
            {
                f[u][j][k] = max(f[u][j][k], f[v][cnt[v]][s] + f[u][j - 1][k - s - 1] + w[i]);
            }
        }
    }
}

int main()
{
    cin >> n >> q;
    for(int i = 1; i < n; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w), add(v, u, w);
    }
    dfs(1, 0);
    cout << f[1][cnt[1]][q];
    return 0;
}

二、二维解法：

1、状态表示

设f[i][j]表示以i为根的子树中选总树枝数量不超过j时的最大苹果数

2、状态转移

设根节点u，对于u的每一个子节点v，有递推关系

枚举u的所有子树v (对应分组背包的一个分组)

  枚举从树中可以选的最大边数j：q~0 （对应背包的体积，倒着遍历因为实际省掉了组这一维）

    枚举可以从子树v中选择的边数k：0~j-1，最多是j-1因为u->v的边要单独算 （对应一组中的一种物品）

      f[u][j] = max(f[u][j], f[v][k] + f[u][j - k - 1] + w[u->v]);

3、初始化：f[1][0] = 0

4、结果：f[1][q]

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 105, M = 205;
int head[N], to[M], w[M], nxt[M], idx;
int f[N][N]; //f[i][j]表示以i为根的子树中选总树枝数量不超过j时的最大苹果数
int n, q;

void add(int a, int b, int c)
{
    to[++idx] = b;
    w[idx] = c;
    nxt[idx] = head[a];
    head[a] = idx;
}

void dfs(int u, int p)
{
    for(int i = head[u]; i; i = nxt[i])
    {
        int v = to[i];
        if(v == p) continue;
        dfs(v, u);

        for(int j = q; j >= 0; j--)
        {
            for(int k = 0; k < j; k++)
            {
                f[u][j] = max(f[u][j], f[v][k] + f[u][j - k - 1] + w[i]);
            }
        }
    }
}

int main()
{
    cin >> n >> q;
    for(int i = 1; i < n; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w), add(v, u, w);
    }
    dfs(1, 0);
    cout << f[1][q];
    return 0;
}