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

2024-02-18 12:12
文章标签 搜索 深度 图论 价格 优先 总和 最小化 旅行 2646

本文主要是介绍【深度优先搜索】【图论】【树】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++**实现。

这篇关于【深度优先搜索】【图论】【树】2646. 最小化旅行的价格总和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/721125。

相关文章

Go中sync.Once源码的深度讲解

Go中sync.Once源码的深度讲解

《Go中sync.Once源码的深度讲解》sync.Once是Go语言标准库中的一个同步原语,用于确保某个操作只执行一次,本文将从源码出发为大家详细介绍一下sync.Once的具体使用,x希望对大家有... 目录概念简单示例源码解读总结概念sync.Once是Go语言标准库中的一个同步原语，用于确保某个操
阅读更多...
五大特性引领创新! 深度操作系统 deepin 25 Preview预览版发布

五大特性引领创新! 深度操作系统 deepin 25 Preview预览版发布

《五大特性引领创新!深度操作系统deepin25Preview预览版发布》今日，深度操作系统正式推出deepin25Preview版本，该版本集成了五大核心特性：磐石系统、全新DDE、Tr... 深度操作系统今日发布了 deepin 25 Preview，新版本囊括五大特性：磐石系统、全新 DDE、Tree
阅读更多...
Node.js 中 http 模块的深度剖析与实战应用小结

Node.js 中 http 模块的深度剖析与实战应用小结

《Node.js中http模块的深度剖析与实战应用小结》本文详细介绍了Node.js中的http模块,从创建HTTP服务器、处理请求与响应,到获取请求参数,每个环节都通过代码示例进行解析,旨在帮... 目录Node.js 中 http 模块的深度剖析与实战应用一、引言二、创建 HTTP 服务器：基石搭建（一
阅读更多...
C# ComboBox下拉框实现搜索方式

C# ComboBox下拉框实现搜索方式

《C#ComboBox下拉框实现搜索方式》文章介绍了如何在加载窗口时实现一个功能,并在ComboBox下拉框中添加键盘事件以实现搜索功能,由于数据不方便公开,作者表示理解并希望得到大家的指教... 目录C# ComboBox下拉框实现搜索步骤一步骤二步骤三总结C# ComboBox下拉框实现搜索步骤一这
阅读更多...
认识、理解、分类——acm之搜索

认识、理解、分类——acm之搜索

普通搜索方法有两种：1、广度优先搜索；2、深度优先搜索； 更多搜索方法： 3、双向广度优先搜索； 4、启发式搜索（包括A*算法等）； 搜索通常会用到的知识点：状态压缩（位压缩，利用hash思想压缩）。
阅读更多...
hdu1240、hdu1253（三维搜索题）

hdu1240、hdu1253（三维搜索题）

1、从后往前输入，（x，y，z）; 2、从下往上输入，（y , z, x）; 3、从左往右输入，（z，x，y）； hdu1240代码如下： #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc
阅读更多...
hdu1180（广搜+优先队列）

hdu1180（广搜+优先队列）

此题要求最少到达目标点T的最短时间，所以我选择了广度优先搜索，并且要用到优先队列。 另外此题注意点较多，比如说可以在某个点停留，我wa了好多两次，就是因为忽略了这一点，然后参考了大神的思想，然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<
阅读更多...
poj 3190 优先队列+贪心

poj 3190 优先队列+贪心

题意： 有n头牛，分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面，并且每个stall每次只能占用一头牛。 问最少需要多少个stall，并输出每头牛所在的stall。 e.g 样例： INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s
阅读更多...
poj 2431 poj 3253 优先队列的运用

poj 2431 poj 3253 优先队列的运用

poj 2431： 题意： 一条路起点为0， 终点为l。 卡车初始时在0点，并且有p升油，假设油箱无限大。 给n个加油站，每个加油站距离终点 l 距离为 x[i]，可以加的油量为fuel[i]。 问最少加几次油可以到达终点，若不能到达，输出-1。 解析： 《挑战程序设计竞赛》： “在卡车开往终点的途中，只有在加油站才可以加油。但是，如果认为“在到达加油站i时，就获得了一
阅读更多...
hdu 4517 floyd+记忆化搜索

hdu 4517 floyd+记忆化搜索

题意： 有n（100）个景点，m（1000）条路，时间限制为t（300），起点s，终点e。 访问每个景点需要时间cost_i，每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问，并且当前点的访问价值应该严格大于前一个访问的点。 现在求，从起点出发，到达终点，在时间限制内，能得到的最大
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2