当前位置：首页 > article >正文

二叉苹果树

article 2024/11/3 0:37:22

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;
}