算法提高课汇总

算法思路

为保证确定留下树枝后所有苹果🍎与1号节点均联通, 对于节点(苹果)$u$, 若保留$u$, 则必须保留
其父节点$father(u)$. 如果将树枝$(u, father(u))$上的苹果转移到$u$上, 问题转变为有依赖的背包问题.

此时每个节点的体积为1, 总体积为保留的树枝数, 价值为🍎数量.

$DP$分析

具体思路参考 AcWing 10. 有依赖的背包问题 .

状态表示$dp(u, j)$

• 集合: 以$u$为根节点, 可保留树枝数为$j$的所有保留方案.

• 属性: Max苹果数量.

状态计算

• 对于线性$DP$, 我们每次考虑第$i$个物品和前$i - 1$个物品状态; 对于树形$DP$, 我们每次考虑
  当前节点$u$的状态与以其子节点为根的子树的状态.

• 将每个子树看作是一个物品组, 每个物品可选方案为$0\sim j - 1$ — 分配的体积. 注意此时
  我们省去了一维状态, 所以与线性分组背包降维代码类似, 我们先枚举物品组, 再从大到小枚举体积.

具体实现

#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 110, M = 2 * N;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dp[N][N]; //dp[u][j]

void add(int u, int v, int c)
{
    e[idx] = v, w[idx] = c, ne[idx] = h[u], h[u] = idx ++ ;
}

void dfs(int u, int father)
{
    for ( int i = h[u]; ~i; i = ne[i] ) //物品组
    {
        int v = e[i];
        if ( v == father )  continue;
        dfs(v, u); //自底向上
        for ( int j = m; j >= 0; j -- ) //体积
            for ( int k = 0; k < j; k ++ ) //分配给子树(某物品组)的体积
            {
                //(u, v)需要占一体积 或者说选择v物品需要1体积
                dp[u][j] = max(dp[u][j], dp[u][j - k - 1] + dp[v][k] + w[i]);
            }
    }
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for ( int i = 1; i < n; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    int root = 1;
    dfs(root, -1);
    cout << dp[root][m] << endl;

    return 0;
}