二叉苹果树

image-20241102203449843
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++;
}
  • 该函数通过邻接表方式添加边。ab 的边权重为 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]uver 的边权。
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 条边所能获得的最大权重和。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/907233.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Linux基础命令(八) 之 alias ,history,stat,type,特殊符号及命令行快捷键

目录 一&#xff0c;命令别名 alias 常见用法 二&#xff0c;命令历史 history 参数及其作用 常见用法 三.显示文件或文件系统的详细信息 stat 参数及其作用 常见用法 四&#xff0c;显示命令的类型 type 参数及其作用 常见用法 五&#xff0c;特殊符号及命令行快捷…

省级-知识产权保护指数(2012-2022年)

省级知识产权保护指数&#xff08;以下简称“指数”&#xff09;正是衡量各省份在知识产权保护方面表现的一个综合指标&#xff0c;它涵盖了立法、执法、审查和监督等多个维度&#xff0c;全面反映了各省份在知识产权保护方面的综合实力。 2012年-2022年省级-知识产权保护指数…

GraphQL 与 Elasticsearch 相遇:使用 Hasura DDN 构建可扩展、支持 AI 的应用程序

作者&#xff1a;来自 Elastic Praveen Durairaju GraphQL 提供了一种高效且灵活的数据查询方式。本博客将解释 Hasura DDN 如何与 Elasticsearch 配合使用&#xff0c;以实现高性能和元数据驱动的数据访问。 此示例的代码和设置可在此 GitHub 存储库 - elasticsearch-subgraph…

filebeat+elasticsearch+kibana日志分析

1 默认配置 1.1 filebeat filebeat-7.17.yml,从网关中下载k8s的配置&#xff0c;指定es和kibana的配置 通过kibana查询可以查询到日志了&#xff0c;但此时还不知道具体怎么用。 1.2 kibana 在Discover中创建索引格式&#xff1a;filebeat-*&#xff0c;得到如下图&#xf…

Rust 力扣 - 2090. 半径为 k 的子数组平均值

文章目录 题目描述题解思路题解代码题目链接 题目描述 题解思路 半径为 k 的子数组平均值 等价于 子数组长度为2 * k 1的总和 除于 2 * k 1 我们遍历长度为2 * k 1的窗口&#xff0c;我们只需要记录窗口内的平均值即可 题解代码 impl Solution {pub fn get_averages(num…

uniapp的video视频属性打包app后层级过高

问题&#xff1a;在使用uniapp开发APP时&#xff0c;使用video标签显示视频发现H5可以正常展示&#xff0c;但是打包到APP后&#xff0c;它的层级过高&#xff0c;把底部导航都盖住了。 官网说明&#xff1a;uni-app官网 官网给了cover-view组件或plus.nativeObj.view、subNVue…

浅谈UI自动化

⭐️前言⭐️ 本篇文章围绕UI自动化来展开&#xff0c;主要内容包括什么是UI自动化&#xff0c;常用的UI自动化框架&#xff0c;UI自动化原理等。 &#x1f349;欢迎点赞 &#x1f44d; 收藏 ⭐留言评论 &#x1f349;博主将持续更新学习记录收获&#xff0c;友友们有任何问题…

Vue3+Data-V实现可视化大屏页面布局

目录 一、前言 二、环境准备 1.Vue3安装npm create vuelatest 2.Data-V配置 项目Data-v安装 main.js中注册Data-v到全局 ​编辑可使用按需引入 3.测试 三、导航栏路由跳转配置 1.子组件mainNav组件准备 2.父组件准备导航栏参数传递 3.子组件接收父组件参数 4.导航…

Python 使用 LSTM 进行情感分析:处理文本序列数据的指南

使用 LSTM 进行情感分析&#xff1a;处理文本序列数据的指南 长短期记忆网络&#xff08;LSTM&#xff09;是一种适合处理序列数据的深度学习模型&#xff0c;广泛应用于情感分析、语音识别、文本生成等领域。它通过在训练过程中“记住”过去的数据特征来理解和预测序列数据的…

树莓派5实时时钟(RTC)

树莓派5板载一个实时时钟模块。它可以通过 USB-C 电源插口右侧板上的 J5(BAT) 插口进行电池供电。如果没有互联网连接来通过 NTP 获取时间&#xff0c;RTC 可能会很有用。 可以设置唤醒警报&#xff0c;将树莓派5切换到非常低功耗的状态&#xff08;大约3mA&#xff09;。当到达…

保姆级教程!!教你通过【Pycharm远程】连接服务器运行项目代码

小罗碎碎念 这篇文章主要解决一个问题——我有服务器&#xff0c;但是不知道怎么拿来写代码&#xff0c;跑深度学习项目。确实&#xff0c;玩深度学习的成本比较高&#xff0c;无论是前期的学习成本&#xff0c;还是你需要具备的硬件成本&#xff0c;都是拦路虎。小罗没有办法…

Chrome与夸克的安全性对比

在当今数字化时代&#xff0c;浏览器的安全性对于用户来说至关重要。Chrome和夸克作为两款流行的浏览器&#xff0c;各有其特点和优势。本文将对这两款浏览器的安全性进行详细对比&#xff0c;帮助用户更好地了解它们之间的差异。&#xff08;本文由https://www.chromegw.com/的…

ZFC in LEAN 之 前集(Pre-set)

前集&#xff08;Pre-set&#xff09;的概念是相对于集合&#xff08;Set&#xff09;&#xff0c;由数学家 Bishop 提出的。Bishop 认为定义一个集合需要三个步骤&#xff1a; 1. 定义该集合的元素是如何构建的&#xff08;Construction&#xff09;。 2. 定义集合中的两元素的…

libaom 源码分析:AV1帧内预测 CfL 模式

CfL预测模式原理 从亮度到色度CfL 是一种色度帧内预测模式&#xff0c;通过建立共位重建亮度采样的线性函数来模拟色度采样&#xff1b;对于不同的色度采样格式&#xff08;例如4:2:0和4:2:2&#xff09;&#xff0c;可能需要对重建的亮度像素进行子采样&#xff0c;以匹配色度…

C++核心编程和桌面应用开发 第十八天(一元/二元谓词 内建函数对象 算术/关系/逻辑仿函数 函数适配器/取反适配器/函数指针适配器/成员函数适配器)

目录 1.函数对象 1.1函数对象特点 2.谓词 2.1一元谓词 2.2二元谓词 3.内建函数对象 3.1算术仿函数 3.2关系仿函数 3.3逻辑仿函数 4.函数适配器 5.取反适配器 5.1一元取反适配器 5.2二元取反适配器 6.函数指针适配器 7.成员函数适配器 1.函数对象 概念&#xff…

Java后端面试内容总结

先讲项目背景&#xff0c;再讲技术栈模块划分&#xff0c; 讲业务的时候可以先讲一般再特殊 为什么用这个&#xff0c;好处是什么&#xff0c;应用场景 Debug发现问题/日志发现问题. QPS TPS 项目单元测试&#xff0c;代码的变更覆盖率达到80%&#xff0c;项目的复用性高…

P3-2.【结构化程序设计】第二节——知识要点:多分支选择语句

讲解视频&#xff1a; P3-2.【结构化程序设计】第二节——知识要点&#xff1a;多分支选择语句 知识要点&#xff1a;多分支选择语句 一、任务分析 已知某公司员工的保底薪水为500&#xff0c;某月销售商品的利润profit(整数)与利润提成的关系如下(单位&#xff1a;元)&#…

关于Android Studio Koala Feature Drop | 2024.1.2下载不了插件的解决办法

解决 androidStudio Settings->Plugins下载插件&#xff0c;点击install后没反应&#xff0c;同时插件描述相关显示不出来 第一步&#xff1a; 第二步&#xff1a; 点击设置&#xff0c;勾选Auto-detect proxy settings&#xff0c;输入网址 https://plugins.jetbrains.com…

UE中查“资源包因何变脏”的方式

“脏”&#xff08;Dirty&#xff09;的意思 当用户对一个资源包&#xff08;关卡&#xff0c;或材质等美术资源&#xff09;做出了修改&#xff0c;变得与磁盘上存储的内容有差异时&#xff0c;UE会对其“标脏”&#xff08;Mark Dirty&#xff09;&#xff0c;显示为 * 符号…

leetcode 2710 移除字符串中的尾随零

1.题目要求: 2.题目代码: class Solution { public:string removeTrailingZeros(string num) {while(num[num.size() - 1] 0){num.pop_back();}return num;} };