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
条边所能获得的最大权重和。