【C++图论 BFS算法】2467. 树上最大得分和路径|2053

本文涉及知识点

C++图论
C++BFS算法

LeetCode2467. 树上最大得分和路径

一个 n 个节点的无向树，节点编号为 0 到 n - 1 ，树的根结点是 0 号节点。给你一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] ，表示节点 ai 和 bi 在树中有一条边。
在每一个节点 i 处有一扇门。同时给你一个都是偶数的数组 amount ，其中 amount[i] 表示：
如果 amount[i] 的值是负数，那么它表示打开节点 i 处门扣除的分数。
如果 amount[i] 的值是正数，那么它表示打开节点 i 处门加上的分数。
游戏按照如下规则进行：
一开始，Alice 在节点 0 处，Bob 在节点 bob 处。
每一秒钟，Alice 和 Bob 分别 移动到相邻的节点。Alice 朝着某个 叶子结点 移动，Bob 朝着节点 0 移动。
对于他们之间路径上的 每一个 节点，Alice 和 Bob 要么打开门并扣分，要么打开门并加分。注意：
如果门 已经打开 （被另一个人打开），不会有额外加分也不会扣分。
如果 Alice 和 Bob 同时 到达一个节点，他们会共享这个节点的加分或者扣分。换言之，如果打开这扇门扣 c 分，那么 Alice 和 Bob 分别扣 c / 2 分。如果这扇门的加分为 c ，那么他们分别加 c / 2 分。
如果 Alice 到达了一个叶子结点，她会停止移动。类似的，如果 Bob 到达了节点 0 ，他也会停止移动。注意这些事件互相 独立 ，不会影响另一方移动。
请你返回 Alice 朝最优叶子结点移动的 最大 净得分。
示例 1：

输入：edges = [[0,1],[1,2],[1,3],[3,4]], bob = 3, amount = [-2,4,2,-4,6]
输出：6
解释：
上图展示了输入给出的一棵树。游戏进行如下：

• Alice 一开始在节点 0 处，Bob 在节点 3 处。他们分别打开所在节点的门。
  Alice 得分为 -2 。
• Alice 和 Bob 都移动到节点 1 。
  因为他们同时到达这个节点，他们一起打开门并平分得分。
  Alice 的得分变为 -2 + (4 / 2) = 0 。
• Alice 移动到节点 3 。因为 Bob 已经打开了这扇门，Alice 得分不变。
  Bob 移动到节点 0 ，并停止移动。

Alice 移动到节点 4 并打开这个节点的门，她得分变为 0 + 6 = 6 。
现在，Alice 和 Bob 都不能进行任何移动了，所以游戏结束。
Alice 无法得到更高分数。
示例 2：

输入：edges = [[0,1]], bob = 1, amount = [-7280,2350]
输出：-7280
解释：
Alice 按照路径 0->1 移动，同时 Bob 按照路径 1->0 移动。
所以 Alice 只打开节点 0 处的门，她的得分为 -7280 。

提示：
2 <= n <= 10⁵
edges.length == n - 1
edges[i].length == 2
0 <= ai, bi < n
ai != bi
edges 表示一棵有效的树。
1 <= bob < n
amount.length == n
amount[i] 是范围 [-10⁴, 10⁴] 之间的一个 偶数 。

BFS

本方法用BFS代替DFS，来达到提速的目的。时间复杂度：O(m)，m是边的数量。
一，将边转成邻接表neiBo。
二，BFS邻接表获取各节点层次leve。
三，通过各节点层次获取各层次包括节点leveNodes。
四，通过边和节点层次获取各节点的父节点pars。
五，通过par节点bob到达各节点时间bomTime，无法到达为n+1。
六，层次从小到大处理个节点。ans[cur]记录alice到达时的得分：父节点的得分+本节点得法。如果leve > bomTime[cur]，不得分；相等，得一半的分；小于，得全分。
七，求ans[cur]的最大值，cur是叶子节点。 如果只有一个节点，唯一的节点是根，也是叶子。否则，根不是叶子，其它节点是否是叶子节点 ⟺ \iff ⟺ neiBo[cur].size()是否是1。

代码

核心代码

classCNeiBo{public:static vector<vector<int>>Two(int n, vector<vector<int>>& edges,bool bDirect,int iBase =0){ vector<vector<int>>vNeiBo(n);for(constauto& v : edges){ vNeiBo[v[0]- iBase].emplace_back(v[1]- iBase);if(!bDirect){ vNeiBo[v[1]- iBase].emplace_back(v[0]- iBase);}}return vNeiBo;}static vector<vector<std::pair<int,int>>>Three(int n, vector<vector<int>>& edges,bool bDirect,int iBase =0){ vector<vector<std::pair<int,int>>>vNeiBo(n);for(constauto& v : edges){ vNeiBo[v[0]- iBase].emplace_back(v[1]- iBase, v[2]);if(!bDirect){ vNeiBo[v[1]- iBase].emplace_back(v[0]- iBase, v[2]);}}return vNeiBo;}static vector<vector<int>>Mat(vector<vector<int>>& neiBoMat){ vector<vector<int>>neiBo(neiBoMat.size());for(int i =0; i < neiBoMat.size(); i++){for(int j = i +1; j < neiBoMat.size(); j++){if(neiBoMat[i][j]){ neiBo[i].emplace_back(j); neiBo[j].emplace_back(i);}}}return neiBo;}};classCBFSLeve{public:static vector<int>Leve(const vector<vector<int>>& neiBo, vector<int> start){ vector<int>leves(neiBo.size(),-1);for(constauto& s : start){ leves[s]=0;}for(int i =0; i < start.size(); i++){for(constauto& next : neiBo[start[i]]){if(-1!= leves[next]){continue;} leves[next]= leves[start[i]]+1; start.emplace_back(next);}}return leves;}template<classNextFun>static vector<int>Leve(int N,NextFun nextFun, vector<int> start){ vector<int>leves(N,-1);for(constauto& s : start){ leves[s]=0;}for(int i =0; i < start.size(); i++){auto nexts =nextFun(start[i]);for(constauto& next : nexts){if(-1!= leves[next]){continue;} leves[next]= leves[start[i]]+1; start.emplace_back(next);}}return leves;}static vector<vector<int>>LeveNodes(const vector<int>& leves){constint iMaxLeve =*max_element(leves.begin(), leves.end()); vector<vector<int>>ret(iMaxLeve +1);for(int i =0; i < leves.size(); i++){ ret[leves[i]].emplace_back(i);}return ret;};};classSolution{public:intmostProfitablePath(vector<vector<int>>& edges,int bob, vector<int>& amount){constint N = amount.size();auto neiBo =CNeiBo::Two(N, edges,false);auto leves =CBFSLeve::Leve(neiBo,{0});auto leveNodes =CBFSLeve::LeveNodes(leves); vector<int>par(N,-1);for(constauto& v : edges){if(leves[v[0]]< leves[v[1]]){ par[v[1]]= v[0];}else{ par[v[0]]= v[1];}} vector<int>bomTime(N, N +1);for(int i =0; bob !=-1; bob = par[bob], i++){ bomTime[bob]= i;} vector<int>ans(N);for(int i =0; i < leveNodes.size();i++){constauto& nodes = leveNodes[i];for(constauto& cur : nodes){if(-1!= par[cur]){ans[cur]+= ans[par[cur]];}if(bomTime[cur]< i){continue;}if(bomTime[cur]> i){ ans[cur]+= amount[cur];}else{ ans[cur]+= amount[cur]/2;}}}int iAns = INT_MIN;for(int i =1; i < N; i++){if(neiBo[i].size()!=1)continue; iAns =max(iAns, ans[i]);}return iAns;}};

单元测试

vector<vector<int>> edges;int bob ; vector<int> amount;TEST_METHOD(TestMethod1){ edges ={{0,1},{1,2},{1,3},{3,4}}, bob =3, amount ={-2,4,2,-4,6};auto res =Solution().mostProfitablePath(edges, bob, amount);AssertEx(6, res);}TEST_METHOD(TestMethod2){ edges ={{0,1}}, bob =1, amount ={-7280,2350};auto res =Solution().mostProfitablePath(edges, bob, amount);AssertEx(-7280, res);}

扩展阅读

视频课程

先学简单的课程，请移步ZEEKLOG学院，听白银讲师（也就是鄙人）的讲解。
https://edu.ZEEKLOG.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.ZEEKLOG.net/lecturer/6176

测试环境

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