【深度优先搜索】【图论】【树】2646. 最小化旅行的价格总和

作者推荐

【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字

涉及知识点

深度优先搜索 图论 树

LeetCode2646. 最小化旅行的价格总和

现有一棵无向、无根的树，树中有 n 个节点，按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。
每个节点都关联一个价格。给你一个整数数组 price ，其中 price[i] 是第 i 个节点的价格。
给定路径的 价格总和 是该路径上所有节点的价格之和。
另给你一个二维整数数组 trips ，其中 trips[i] = [starti, endi] 表示您从节点 starti 开始第 i 次旅行，并通过任何你喜欢的路径前往节点 endi 。
在执行第一次旅行之前，你可以选择一些 非相邻节点 并将价格减半。
返回执行所有旅行的最小价格总和。
示例 1：
输入：n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]
输出：23
解释：
上图表示将节点 2 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 、2 和 3 并使其价格减半后的树。
第 1 次旅行，选择路径 [0,1,3] 。路径的价格总和为 1 + 2 + 3 = 6 。
第 2 次旅行，选择路径 [2,1] 。路径的价格总和为 2 + 5 = 7 。
第 3 次旅行，选择路径 [2,1,3] 。路径的价格总和为 5 + 2 + 3 = 10 。
所有旅行的价格总和为 6 + 7 + 10 = 23 。可以证明，23 是可以实现的最小答案。
示例 2：
输入：n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]
输出：1
解释：
上图表示将节点 0 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 并使其价格减半后的树。
第 1 次旅行，选择路径 [0] 。路径的价格总和为 1 。
所有旅行的价格总和为 1 。可以证明，1 是可以实现的最小答案。
提示：
1 <= n <= 50
edges.length == n - 1
0 <= ai, bi <= n - 1
edges 表示一棵有效的树
price.length == n
price[i] 是一个偶数
1 <= price[i] <= 1000
1 <= trips.length <= 100
0 <= starti, endi <= n - 1

两次深度优先搜索

深度优先搜索计算进过各节点多少次

以任何一个节点（比如：0）为整课树的节点，有如下性质：
性质一：路径一定是：起点 → \rightarrow → 公共祖先 → \rightarrow → 终点 特例是：起点或终点就是公共祖先。
性质二：如果某棵子树包括某次旅行的起点或终点，则此次旅行必定经过此子树根节点。如果起点和终点都是此子树的节点，也算。 之后就不算了。
如何判断 节点是否属于子树：
DFS 的开始，给节点编号（访问编号）m_vTime[cur]，从1到大。没有访问就是默认值0。
DFS结束时，访问编号大于等于m_vTime[cur]，是本子树的节点。
m_vNeedVis 记录各节点访问的需要访问的次数。
m_vHasDo 记录那些旅行的公共祖先已经访问。

深度优先搜索枚举半价

{ 子节点节点全价 根节点半价 m i n ( 子节点节点全价，子节点节点半价 ) 根节点全价 \begin{cases} 子节点节点全价 & 根节点半价 \\ min(子节点节点全价，子节点节点半价) & 根节点全价 \\ \end{cases} {子节点节点全价min(子节点节点全价，子节点节点半价)​根节点半价根节点全价​
DFS2返回值两个：
一，全价、半价的较小值。
二，全价的最小值。

代码

核心代码

class CNeiBo2
{
public:
	CNeiBo2(int n, bool bDirect, int iBase = 0) :m_iN(n), m_bDirect(bDirect), m_iBase(iBase)
	{
		m_vNeiB.resize(n);
	}
	CNeiBo2(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) :m_iN(n), m_bDirect(bDirect), m_iBase(iBase)
	{
		m_vNeiB.resize(n);
		for (const auto& v : edges)
		{
			m_vNeiB[v[0] - iBase].emplace_back(v[1] - iBase);
			if (!bDirect)
			{
				m_vNeiB[v[1] - iBase].emplace_back(v[0] - iBase);
			}
		}
	}
	inline void Add(int iNode1, int iNode2)
	{
		iNode1 -= m_iBase;
		iNode2 -= m_iBase;
		m_vNeiB[iNode1].emplace_back(iNode2);
		if (!m_bDirect)
		{
			m_vNeiB[iNode2].emplace_back(iNode1);
		}
	}
	const int m_iN;
	const bool m_bDirect;
	const int m_iBase;
	vector<vector<int>> m_vNeiB;
};

class Solution {
public:
	int minimumTotalPrice(int n, vector<vector<int>>& edges, vector<int>& price, vector<vector<int>>& trips) {
		CNeiBo2 neiBo(n, edges, false);
		m_vNeedVis.resize(n);
		m_vHasDo.resize(trips.size());
		m_vTime.resize(n);
		m_trips = trips;
		m_price = price;
		DFS(neiBo.m_vNeiB, 0, -1);
		return DFS2(neiBo.m_vNeiB, 0, -1).first;
	}
	void DFS(vector<vector<int>>& neiBo, int cur, int par)
	{
		m_vTime[cur] = ++m_llTime;
		for (const auto& next : neiBo[cur])
		{
			if (next == par)
			{
				continue;
			}
			DFS(neiBo, next, cur);
		}
		for (int i = m_trips.size()-1 ; i >=0 ; i--)
		{
			if (m_vHasDo[i])
			{
				continue;
			}
			const auto& v = m_trips[i];
			if ((m_vTime[v[0]] >= m_vTime[cur]) || (m_vTime[v[1]] >= m_vTime[cur]))
			{
				m_vNeedVis[cur]++;
				if ((m_vTime[v[0]] >= m_vTime[cur]) && (m_vTime[v[1]] >= m_vTime[cur]))
				{ 
					m_vHasDo[i] = true;
				}
			}
		}
	}
	pair<int,int> DFS2(vector<vector<int>>& neiBo, int cur, int par)
	{
		int  i2 = m_price[cur]*m_vNeedVis[cur],i1 =i2/2;
		for (const auto& next : neiBo[cur])
		{
			if (next == par)
			{
				continue;
			}
			auto [i11,i21] = DFS2(neiBo, next, cur);
			i1 += i21;
			i2 += i11;
		}
		return make_pair(min(i1, i2), i2);
	}
	vector<int> m_vNeedVis,m_vTime;// 记录各节点访问的需要访问的次数。
	vector<bool>	m_vHasDo;// 记录那些旅行的公共祖先已经访问。
	int m_llTime = 0;
	vector<vector<int>> m_trips;
	vector<int> m_price;
};

测试用例


template<class T,class T2>
void Assert(const T& t1, const T2& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}

int main()
{	
	int n;
	vector<int>  price;
	vector<vector<int>> edges, trips;
	{
		Solution sln;
		n = 4, edges = { {0,1},{1,2},{1,3} }, price = { 2,2,10,6 }, trips = { {0,3},{2,1},{2,3} };
		auto res = sln.minimumTotalPrice(n, edges, price, trips);
		Assert(res,23);
	}

	{
		Solution sln;
		n = 2, edges = { {0,1} }, price = { 2,2 }, trips = { {0,0} };
		auto res = sln.minimumTotalPrice(n, edges, price, trips);
		Assert(res, 1);
	}
	{
		Solution sln;
		n = 5, edges = { {1,2},{2,0},{0,3},{3,4} }, price = { 12,26,22,12,2 };
		trips = { {3,3},{3,2},{3,0},{3,4},{1,1},{2,2},{4,0},{0,2},{2,3},{2,1},{4,2},{0,1},{4,2},{0,4},{0,3},{4,0},{4,0},{3,3},{4,3},{2,2},{4,2},{1,4},{3,2},{4,4},{4,2},{2,3},{4,3},{4,4},{4,2},{0,4},{4,2},{3,4},{4,0},{3,2},{3,1},{2,0},{0,4},{3,4},{2,0},{1,4},{4,2},{4,4},{2,1},{0,1},{4,1},{3,4},{0,4},{2,0},{2,0},{3,3},{4,4},{0,1},{0,1},{0,1},{2,0},{0,1},{3,1},{3,4},{3,4},{4,2},{0,4},{4,4},{3,2},{2,1},{3,2},{1,4},{1,0},{4,2},{4,3},{3,1},{4,4},{3,1},{1,0},{0,0},{0,0},{3,0},{0,2},{2,2},{3,3},{0,3} };;
		auto res = sln.minimumTotalPrice(n, edges, price, trips);
		Assert(res, 2037);
	}
	
}

2023年3月

class CNeiBo2
{
public:
CNeiBo2(int n, vector<vector>& edges, bool bDirect)
{
m_vNeiB.resize(n);
for (const auto& v : edges)
{
m_vNeiB[v[0]].emplace_back(v[1]);
if (!bDirect)
{
m_vNeiB[v[1]].emplace_back(v[0]);
}
}
}
vector<vector> m_vNeiB;
};
class Solution {
public:
int minimumTotalPrice(int n, vector<vector>& edges, vector& price, vector<vector>& trips) {
m_vParent.resize(n);
CNeiBo2 neBo(n, edges, false);
dfs(0, -1, neBo.m_vNeiB);
vector vTotalPrice(n);
for (const vector& trip : trips)
{
const auto& v0 = m_vParent[trip[0]];
const auto& v1 = m_vParent[trip[1]];
int i = 0;
for (; (i < min(v0.size(), v1.size())) && (v0[i] == v1[i]); i++);
vTotalPrice[v0[i - 1]] += price[v0[i - 1]];
for (int j = i; j < v0.size(); j++)
{
vTotalPrice[v0[j]] += price[v0[j]];
}
for (int j = i; j < v1.size(); j++)
{
vTotalPrice[v1[j]] += price[v1[j]];
}
}
int iRet = std::accumulate(vTotalPrice.begin(), vTotalPrice.end(), 0);
return iRet - MaxDFS(0, -1, neBo.m_vNeiB, vTotalPrice, true);
}
void dfs(int iCur, int iParent, const vector<vector>& vNeiBo)
{
if (-1 != iParent)
{
m_vParent[iCur] = m_vParent[iParent];
}
m_vParent[iCur].emplace_back(iCur);
for (const auto& next : vNeiBo[iCur])
{
if (iParent == next)
{
continue;
}
dfs(next, iCur, vNeiBo);
}
}
int MaxDFS(int iCur, int iParent, const vector<vector>& vNeiBo, const vector& vTotalPrice,bool bCanRoot)
{
int iRet = 0;
for (const auto& next : vNeiBo[iCur])
{
if (iParent == next)
{
continue;
}
iRet += MaxDFS(next, iCur, vNeiBo, vTotalPrice,true);
}
if ((!bCanRoot) || (0 == vTotalPrice[iCur]))
{
return iRet;
}
int iRet2 = vTotalPrice[iCur] / 2;
for (const auto& next : vNeiBo[iCur])
{
if (iParent == next)
{
continue;
}
iRet2 += MaxDFS(next, iCur, vNeiBo, vTotalPrice, false);
}
return max(iRet, iRet2);
}
vector<vector> m_vParent;
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。

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

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

相关文章

elementui 中el-date-picker 选择年后输出的是Wed Jan 01 2025 00:00:00 GMT+0800 (中国标准时间)

elementui 中el-date-picker 选择年后输出的是Wed Jan 01 2025 00:00:00 GMT+0800 (中国标准时间)

文章目录 问题分析 问题 在使用 el-date-picker 做只选择年份的控制器时&#xff0c;出现如下问题&#xff1a;el-date-picker选择年后输出的是Wed Jan 01 2025 00:00:00 GMT0800 (中国标准时间)&#xff0c;输出了两次如下 分析 在 el-date-picker 中&#xff0c;我们使用…
阅读更多...
核心篇 - 集成IS-IS配置实战

核心篇 - 集成IS-IS配置实战

文章目录 一. 实验专题1.1. 实验1&#xff1a;配置单区域集成IS-IS1.1.1. 实验目的1.1.2. 实验拓扑1.1.3. 实验步骤&#xff08;1&#xff09;配置IP地址&#xff08;2&#xff09;配置IS-IS 1.1.4. 实验调试&#xff08;1&#xff09;查看邻接表&#xff08;2&#xff09;查看…
阅读更多...
Elasticsearch从入门到精通

Elasticsearch从入门到精通

目录 &#x1f9c2;1.简单介绍 &#x1f953;2.安装与下载 &#x1f32d;3.安装启动es &#x1f37f;4.安装启动kibana &#x1f95e;5.初步检索 &#x1f9c8;6.进阶检索 &#x1fad3;7.Elasticsearch整合 1.简单介绍&#x1f697;&#x1f697;&#x1f697; Elat…
阅读更多...
使用一根网线，让Ubuntu和正点原子I.MX6ULL开发板互相ping通

使用一根网线，让Ubuntu和正点原子I.MX6ULL开发板互相ping通

1.硬件准备 准备一根网线即可 2. 让windows和I.MX6ULLping通 2.1 找根网线将I.MX6ULL和电脑连起来 2.2 让I.MX6ULL通电运行起来&#xff0c;我这里使用的是正点原子版本的内核、 2.3 进入电脑的网络连接后&#xff0c;按照如下步骤操作 2.4 将ip地址、子网掩码、默认网关…
阅读更多...
数据结构-双指针法

数据结构-双指针法

介绍 双指针法是一种可以在O&#xff08;n&#xff09;时间复杂度内解决数组、链表、字符串等数据结构相关的问题的方法。核心思想为使用两个指针在不同位置遍历数组或链表&#xff0c;从而实现特定操作。 常见的双指针法有 1.快慢指针&#xff1a;快指针每次移动两步&…
阅读更多...
阿里云服务器配置怎么选？CPU内存带宽配置多大？

阿里云服务器配置怎么选？CPU内存带宽配置多大？

阿里云服务器配置怎么选择&#xff1f;根据实际使用场景选择&#xff0c;个人搭建网站可选2核2G配置&#xff0c;访问量大的话可以选择2核4G配置&#xff0c;企业部署Java、Python等开发环境可以选择2核8G配置&#xff0c;企业数据库、Web应用或APP可以选择4核8G配置或4核16G配…
阅读更多...
入门OpenCV：图像阈值处理

入门OpenCV：图像阈值处理

基本概念 图像阈值是一种简单、高效的图像分割方法&#xff0c;目的是将图像转换成二值图像。这个过程涉及比较像素值和阈值&#xff0c;根据比较结果来确定每个像素点的状态&#xff08;前景或背景&#xff09;。图像阈值在处理二维码、文本识别、物体跟踪等领域中非常有用。…
阅读更多...
【前端工程化面试题】webpack proxy的工作原理，为什么能解决跨域问题

【前端工程化面试题】webpack proxy的工作原理，为什么能解决跨域问题

在 webpack 的配置文件 webpack.config.js 中有一个配置项 devServer 里面有一个属性是 proxy&#xff0c;这里面可以配置代理服务器&#xff0c;解决跨域问题&#xff0c;请参考官网。 一般来说 webpack 的代理就是说的开发服务器 webpack-dev-server。 其实不光是 webpack 其…
阅读更多...
“挖矿”系列：细说Python、conda 和 pip 之间的关系

“挖矿”系列：细说Python、conda 和 pip 之间的关系

继续挖矿&#xff0c;挖“金矿”&#xff01; 1. Python、conda 和 pip&#xff08;挖“金矿”工具&#xff09; Python、conda 和 pip 是在现代数据科学和软件开发中常用的工具&#xff0c;它们各自有不同的作用&#xff0c;但相互之间存在密切的关系&#xff1a; Python&…
阅读更多...
AIGC实战——能量模型(Energy-Based Model)

AIGC实战——能量模型(Energy-Based Model)

AIGC实战——能量模型 0. 前言1. 能量模型1.1 模型原理1.2 MNIST 数据集1.3 能量函数 2. 使用 Langevin 动力学进行采样2.1 随机梯度 Langevin 动力学2.2 实现 Langevin 采样函数 3. 利用对比散度训练小结系列链接 0. 前言 能量模型 (Energy-based Model, EBM) 是一类常见的生…
阅读更多...
《PCI Express体系结构导读》随记 —— 第II篇 第13章 PCI总线与虚拟化技术（6）

《PCI Express体系结构导读》随记 —— 第II篇 第13章 PCI总线与虚拟化技术（6）

接前一篇文章&#xff1a;《PCI Express体系结构导读》随记 —— 第II篇 第13章 PCI总线与虚拟化技术&#xff08;5&#xff09; 13.2 ATS&#xff08;Address Translation Services&#xff09; 单纯使用IOMMU并不能充分发挥处理器系统的效率&#xff0c;从图13-2中可以发现&…
阅读更多...
JVM-JVM中对象的生命周期

JVM-JVM中对象的生命周期

申明&#xff1a;文章内容是本人学习极客时间课程所写&#xff0c;文字和图片基本来源于课程资料&#xff0c;在某些地方会插入一点自己的理解&#xff0c;未用于商业用途&#xff0c;侵删。 原资料地址&#xff1a;课程资料 对象的创建 常量池检查:检查new指令是否能在常量池…
阅读更多...
亚马逊测评：揭秘做号的“花招”与“猫腻”，如何避免被割韭菜？

亚马逊测评：揭秘做号的“花招”与“猫腻”，如何避免被割韭菜？

亚马逊测评行业如今如火如荼&#xff0c;吸引了众多朋友投身其中。然而&#xff0c;这个行业也是五花八门&#xff0c;什么样的人和公司都有&#xff0c;让人眼花缭乱。作为卖家&#xff0c;如何选择靠谱的测评服务商是一门必修课&#xff1b;而对于初学者&#xff0c;如何入门…
阅读更多...
TensorRT转换onnx的Transpose算子遇到的奇怪问题

TensorRT转换onnx的Transpose算子遇到的奇怪问题

近来把一个模型导出为onnx并用onnx simplifier化简后转换为TensorRT engine遇到非常奇怪的问题&#xff0c;在我们的网络中有多个检测头时&#xff0c;转换出来的engine的推理效果是正常的&#xff0c;当网络中只有一个检测头时&#xff0c;转换出来的engine的推理效果奇差&…
阅读更多...
PAM | 账户安全 | 管理

PAM | 账户安全 | 管理

PAM PAM&#xff08;Pluggable Authentication Modules&#xff0c;可插入式身份验证模块&#xff09;是一个灵活的身份验证系统&#xff0c;允许我们通过配置和组合各种模块来实现不同的身份验证策略。 在 Linux 或类 Unix 系统中&#xff0c;常见的 PAM 模块包括以下几种类…
阅读更多...
时序预测 | Matlab实现BO-LSSVM贝叶斯算法优化最小二乘支持向量机时间序列预测

时序预测 | Matlab实现BO-LSSVM贝叶斯算法优化最小二乘支持向量机时间序列预测

时序预测 | Matlab实现BO-LSSVM贝叶斯算法优化最小二乘支持向量机时间序列预测 目录 时序预测 | Matlab实现BO-LSSVM贝叶斯算法优化最小二乘支持向量机时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 Matlab实现BO-LSSVM贝叶斯算法优化最小二乘支持向量机时间…
阅读更多...
Open CASCADE学习|直纹曲面（ruled surface）

Open CASCADE学习|直纹曲面（ruled surface）

直纹曲面是一类特殊的曲面&#xff0c;在几何学和微分几何中都有研究。它的主要特性是&#xff0c;曲面上的每一点都有至少一条直线经过。换句话说&#xff0c;直纹曲面可以由一条直线通过连续运动构成。在三维欧几里德空间中&#xff0c;最常见的直纹曲面是平面、柱面和锥面&a…
阅读更多...
JAVA面试框架篇

JAVA面试框架篇

1. Spring refresh 流程 要求 掌握 refresh 的 12 个步骤 Spring refresh 概述 refresh 是 AbstractApplicationContext 中的一个方法&#xff0c;负责初始化 ApplicationContext 容器&#xff0c;容器必须调用 refresh 才能正常工作。它的内部主要会调用 12 个方法&#x…
阅读更多...
Manifest merger failed with multiple errors, see logs

Manifest merger failed with multiple errors, see logs

问题 Manifest merger failed with multiple errors, see logs详细问题 笔者进行Android 项目开发&#xff0c;修改AndroidManifest.xml代码后&#xff0c;控制台报错 AndroidManifest.xml报错核心代码 <manifest><uses-permission android:name"android.perm…
阅读更多...
解码DMAIC：李国武老师的品质与运营之道

解码DMAIC：李国武老师的品质与运营之道

DMAIC&#xff0c;对于许多人来说可能还是一个相对陌生的概念。但如果你是企业界的观察者&#xff0c;或者对提升产品质量有着浓厚的兴趣&#xff0c;那么你一定不能错过这个话题。DMAIC不仅是一种方法论&#xff0c;更是企业实现卓越运营、提升竞争力的关键工具。今天&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023