专栏文章
题解:P1623 [CEOI2007] 树的匹配 Treasury
P1623题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @miqx4pw3
- 此快照首次捕获于
- 2025/12/04 12:11 3 个月前
- 此快照最后确认于
- 2025/12/04 12:11 3 个月前
这段代码解决了一个典型的树形动态规划问题,特别是树的染色问题,求树中选点方案的最大值以及对应的选点方案数。具体来说,代码通过深度优先搜索(DFS)计算每个子树中不选择当前节点或选择当前节点的最大收益及其方案数,并利用递推关系实现树的动态规划。
代码结构与思路
树的结构:输入给定一个树的节点和边,通过邻接表(adj)来表示树的结构。
动态规划数组:
dp[u][0]:表示在子树 u 中,不选择 u 这个节点时,能够获得的最大收益。
dp[u][1]:表示在子树 u 中,选择 u 这个节点时,能够获得的最大收益。
ways[u][0]:表示在子树 u 中,最大收益 dp[u][0] 对应的方案数。
ways[u][1]:表示在子树 u 中,最大收益 dp[u][1] 对应的方案数。
DFS 递归:从根节点(节点 1)开始,递归遍历树的每个节点,通过 DFS 动态计算每个节点的最大收益及其方案数。
动态规划的状态转移:
对于每个子节点 v,更新当前节点 u 的 dp[u][0] 和 dp[u][1]:
dp[u][0] 是当前节点 u 不选的情况下,选择每个子节点的最大收益(无论子节点是否被选)。
dp[u][1] 是当前节点 u 被选的情况下,所有子节点都不能被选(即 dp[v][0])。
更新方案数 ways[u][0] 和 ways[u][1],根据子节点选择的方式来递推。
如果某个子节点选择了不同的方案(即 dp[v][0] 和 dp[v][1] 最大值相同),则需要计算两种方案的总数。
代码详细注释:
code 5分
CPP#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7; // 结果取模的常数
int N; // 节点数
vector<int> adj[1001]; // 邻接表,表示树的结构
int dp[1001][2]; // dp[u][0] -> 不选u时的最大收益,dp[u][1] -> 选u时的最大收益
int ways[1001][2]; // ways[u][0] -> dp[u][0]对应的方案数,ways[u][1] -> dp[u][1]对应的方案数
// 深度优先搜索,递归计算树的最大收益和方案数
void dfs(int u, int parent) {
dp[u][0] = 0; // 初始化:不选u时,最大收益为0
dp[u][1] = 0; // 初始化:选u时,最大收益为0
ways[u][0] = 1; // 初始化:不选u时,方案数为1
ways[u][1] = 0; // 初始化:选u时,方案数为0(初始状态下不可能选择u)
// 遍历当前节点u的所有邻居v
for (int v : adj[u]) {
if (v == parent) continue; // 防止回到父节点,树的深度优先搜索
dfs(v, u); // 递归遍历子节点
// 更新当前节点u不选的情况
dp[u][0] += max(dp[v][0], dp[v][1]); // 最大收益是子节点不选或选的最大值
if (dp[v][0] > dp[v][1]) {
// 如果子节点v不选的最大收益大于选v的最大收益
ways[u][0] = (1LL * ways[u][0] * ways[v][0]) % MOD; // 方案数是子节点不选的方案数的积
} else if (dp[v][0] < dp[v][1]) {
// 如果子节点v选的最大收益大于不选v的最大收益
ways[u][0] = (1LL * ways[u][0] * ways[v][1]) % MOD; // 方案数是子节点选的方案数的积
} else {
// 如果子节点v的最大收益是相同的(即不选v和选v都有相同的收益)
ways[u][0] = (1LL * ways[u][0] * (ways[v][0] + ways[v][1]) % MOD) % MOD; // 方案数是两种选择的方案数之和
}
// 更新当前节点u选的情况
dp[u][1] = dp[u][0] + 1; // 选择u时的最大收益是子节点都不选时的最大收益 + 1
ways[u][1] = ways[u][0]; // 选择u时的方案数是选择u时不选子节点的方案数
}
}
int main() {
cin >> N; // 输入节点数
for (int i = 1; i <= N; i++) {
int u, m; // u为当前节点,m为该节点的邻居数量
cin >> u >> m;
for (int j = 0; j < m; j++) {
int v; // 邻接的节点v
cin >> v;
adj[u].push_back(v); // 添加边到邻接表
adj[v].push_back(u); // 因为是无向图,反向边也要添加
}
}
// 从根节点1开始执行DFS
dfs(1, -1);
// 输出结果
cout << dp[1][0] << endl; // 从根节点开始,不选根节点时的最大收益
cout << ways[1][0] << endl; // 从根节点开始,不选根节点时的最大收益对应的方案数
return 0;
}
主要部分解析:
邻接表的构建:树的边输入后,构建邻接表 adj[u],表示节点 u 和它的所有邻居之间的连接。
DFS 树的遍历:从根节点(节点 1)开始,递归计算每个节点的最大收益及其对应的方案数。
动态规划状态转移:
dp[u][0] 表示在子树 u 中,不选择 u 的最大收益。
dp[u][1] 表示在子树 u 中,选择 u 的最大收益。
ways[u][0] 和 ways[u][1] 分别记录对应的方案数。
状态转移解释:当选择当前节点时,需要从子节点的“未选择”和“选择”状态中取最大值,进行方案数的合并。
时间复杂度分析:
时间复杂度:O(N),因为 DFS 访问每个节点和每条边的时间复杂度是 O(1),整个树的节点数和边数为 O(N),因此总复杂度为 O(N)。
空间复杂度:O(N),需要 O(N) 空间来存储邻接表和动态规划数组。
总结:
该代码利用 DFS 和动态规划解决了一个树形结构中的最大选择问题(类似“树的独立集”问题),同时通过记录每个状态的方案数,能够有效地计算出选择方案的数量。管理员,求过求过!
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...