网站用户权限,公司网站怎么建站,高端vi设计机构,百度wap网站建设题目传送门#xff1a;
P2996 [USACO10NOV] Visiting Cows G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
前言#xff1a;
本题的核心问题是在一棵由奶牛#xff08;节点#xff09;和道路#xff08;边#xff09;构成的树状结构中#xff0c;根据 “不能同时拜…题目传送门
P2996 [USACO10NOV] Visiting Cows G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
前言
本题的核心问题是在一棵由奶牛节点和道路边构成的树状结构中根据 “不能同时拜访直接相连的两个奶牛” 这一限制条件找出贝茜能够拜访的奶牛的最大数量难度为中下一点。
#本题具体思路和步骤 1、问题抽象与数据结构选择 1.1、输的抽象 题目中提到了 N 个奶牛 我们通过 N - 1 条道路相连并且任意两头奶牛之间的连接关系可以抽象成一棵树每头奶牛是数的一个节点道路是树的边。 1.2、邻接表存储 为了表示这棵树我们使用邻接表来存储节点之间的连接关系。邻接表是一种常用的图树是一种特殊的图的存储方式对于每个节点 u使用一个数组 adj[u] 来存储与它直接相连的所有节点。 2、动态Dp思想引入 1.1、状态定义 设 dp[u][o] 表示不选组该节点 u 时以 u 为根的子树中可拜访最大奶牛数量。 设 dp[u][1] 表示x厕节点 u 时以 u 为根的子树中可拜访的最大奶牛数量。 1.2、状态转移的核心思路 我们通过递归地考虑每个节点及其子节点的选择情况利用子问题的解来构建当前节点的解。 3、状态转移方程推导 1.1、不选择节点 u 的情况 当不选择节点 u 时对于 u 的每个节点 v 我们可以自由选择是否拜访 v 。因为不选 u 不会对 v 的选择产生直接限制所以我们要在 v 选择 dp[v][1] 和不被选择 dp[v][0] 这两种情况中取最大值然后将所有子节点的这些最大值累加起来就得到了 dp[u][0] 这两种情况中取最大值然后将所有子节点的这些最大值累加起来就得到了 dp[u][0]。即 dp[u][0]sum(max(dp[v][0],dp[v][1]))这里的 sum 表示为 u 的所有子节点 v 进行累加。 1.2、选择节点 u 的情况 当选择节点 u 时根据题目要求与 u 直接相连的子节点都不能被选择。所以 u 的子节点 v 只能处于不被选择的状态。我们先将节点 u 本身计入然后把所有子节点不被选择状态下的数量累加起来就得到了 dp[u][1]。即 dp[u][1]1sum(dp[v][0])。 4、深度优先搜索实现 1.1、递归遍历树 使用深度优先搜索算法来遍历整棵树。从树的任意一个节点开始递归地访问每个节点及其子节点。 1.2、计算 dp 值 在递归访问的过程中对于每个节点 u 先初始化 dp[u][0]0 和 dp[u][1]1。然后遍历 u 的所有子节点 v 根据上述状态转移方程更新 dp[u][0] 和 dp[u][1] 的值 5、结果计算 整棵树遍历完成后最终的结果就是根节点在选择何不选择当中两种状态下可拜访奶牛数量的最大值即 max(dp[1][0],dp[1][1])。
##复杂度分析 1、时间复杂度 由于深度搜索会遍历树中的每个节点和每条边一次树有 n 个节点和 n - 1 条边所以时间复杂度为 O(n)。 2、空间复杂度 主要的空间开销在于邻接表和 dp 数组。邻接表存储树的结果需要 O(n) 的空间 dp 数组存储每个节点的两种状态也需要 O(n) 的空间因此空间复杂度为 O(n)。
###代码
#include bits/stdc.h
using namespace std;const int MAXN 50005;
vectorint adj[MAXN]; // 邻接表存储树的结构
int dp[MAXN][2]; // dp数组dp[u][0] 表示不选节点udp[u][1] 表示选节点u// 深度优先搜索函数用于计算dp数组
void dfs(int u, int p) {dp[u][0] 0;dp[u][1] 1;for (int v : adj[u]) {if (v ! p) {dfs(v, u);dp[u][0] max(dp[v][0], dp[v][1]);dp[u][1] dp[v][0];}}
}int main() {int n;cin n;// 读取边的信息构建树的邻接表for (int i 0; i n - 1; i) {int c1, c2;cin c1 c2;adj[c1].push_back(c2);adj[c2].push_back(c1);}// 从节点1开始进行深度优先搜索dfs(1, 0);// 输出最大可拜访的奶牛数量cout max(dp[1][0], dp[1][1]) endl;return 0;
}
