AcWing 1074. 二叉苹果树【有依赖背包DP】 - AcWing

问题描述

在一棵有权无向树中，从某个节点（这里假设为节点 1）出发，遍历树的子节点，每经过一条边会获得对应的权重值。在访问节点数的限制下（即体积限制），我们希望获得最大的路径权重和。

代码解析

1. 全局变量和常量

const int N = 110, M = N << 1;
int n, m;           // n 表示节点数, m 表示最大访问节点数（体积限制）
int h[N], e[M], w[M], ne[M], idx; // 邻接表
int f[N][N];        // 动态规划数组 f[u][j] 表示以 u 为根的子树中，最多选择 j 条边能得到的最大权重和

• N 是节点数上限，M 是边数的上限。
• h[N]：邻接表的头节点数组，h[u] 表示从 u 出发的第一条边在 e 中的索引。
• e[M]：邻接表存储的边的目标节点数组。
• w[M]：边的权重数组，表示 e[i] 对应边的权重。
• ne[M]：存储下一条边的索引。
• idx：记录当前插入边的位置。
• f[u][j]：动态规划数组，表示以 u 为根的子树中，选择至多 j 条边所能获得的最大权重和。

2. 添加边函数 add

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

• 该函数通过邻接表方式添加边。a 到 b 的边权重为 c，同时更新 h[a] 和 ne 数组。

3. 深度优先搜索 dfs

void dfs(int u, int father) {
    for (int i = h[u]; ~i; i = ne[i]) {
        int ver = e[i];
        if (ver == father) continue;
        dfs(ver, u);
        for (int j = m; j >= 0; j--)
            for (int k = 0; k <= j - 1; k++)
                f[u][j] = max(f[u][j], f[u][j - k - 1] + f[ver][k] + w[i]);
    }
}

• dfs 是核心的递归函数。以节点 u 为根节点，递归处理子树中的路径选择问题。
• 遍历从 u 出发的每一条边，跳过回到父节点的边 father。
• 调用 dfs(ver, u) 递归处理子节点 ver 的子树，计算在 ver 处的最优路径权重。
• 动态规划转移：
  • 外层循环 j：表示从 u 出发选择至多 j 条边。
  • 内层循环 k：枚举当前子节点选择的边数。
  • 转移方程 f[u][j] = max(f[u][j], f[u][j - k - 1] + f[ver][k] + w[i]);：
    • f[u][j]：更新 u 节点的最优解。
    • f[u][j - k - 1]：u 剩余的边数（预留一个选择的子节点跟父节点交互时的链接）。
    • f[ver][k]：子节点 ver 的最优解。
    • w[i]：u 到 ver 的边权。

4. 主函数 main

int main() {
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n; i++) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
    dfs(1, -1);
    printf("%d\n", f[1][m]);
    return 0;
}

• 初始化邻接表头数组 h，设为 -1 表示空。
• 输入节点数 n 和最大体积 m。
• 读取并建立双向边，add(a, b, c) 和 add(b, a, c) 将每条边双向存储。
• 从节点 1 开始进行 DFS，设 -1 为父节点标记，避免重复访问。
• 输出 f[1][m]，即以 1 为根、最多选 m 条边所能获得的最大权重和。