网站域名查询注册自建站平台
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条边所能获得的最大权重和。