思路
不一样
怎么大家都dfs
只剩我bfs了 我是不是很奇怪
我就只会一步一步走
right foot up, left foot slide
class Solution {
public:
int mostProfitablePath(vector<vector<int>>& edges, int bpos, vector<int>& amount) {
int n = edges.size() + 1;
vector<vector<int>> adj(n);
for(auto& e: edges){
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]);
}
vector<bool> seen(n, false);
vector<vector<int>> child(n);
vector<int> parent(n, 0);
find(0, adj, child, parent, seen);
int res = INT_MIN;
//bfs
vector<int> steps(n, -1);
queue<int> q;
q.push(0);
int step = 0;
while(!q.empty()){
queue<int> nq;
bool same = false;
while(!q.empty()){
int nd = q.front();
q.pop();
int add = 0;
if(nd != 0) add = amount[parent[nd]];
if(nd == bpos){
amount[nd] /= 2;
same = true;
}
amount[nd] += add;
if(child[nd].empty()) res = max(res, amount[nd]);
for(auto c: child[nd]){
nq.push(c);
}
}
if(!same) amount[bpos] = 0;
if(bpos != 0) bpos = parent[bpos];
q = nq;
}
return res;
}
void find(int cur, vector<vector<int>>& adj, vector<vector<int>>& child, vector<int>& parent, vector<bool>& seen){
if(seen[cur]) return;
seen[cur] = true;
for(auto& e: adj[cur]){
if(!seen[e]){
child[cur].push_back(e);
parent[e] = cur;
find(e, adj, child, parent, seen);
}
}
}
};
※ 引述《oin1104 (是oin的说)》之铭言：
: ※ 引述 《Rushia (早瀬ユウカの体操服)》 之铭言：
: :
: : https://leetcode.com/problems/most-profitable-path-in-a-tree
: : 2467. Most Profitable Path in a Tree
: : 给你一个大小为n-1的阵列表示边，表示无向图的n个点，alice从0出发，bob从bob出发
: : ，两者同时出发，他们会拿走每个点上面的分数，如果他们遇到了则会平分分数，alice
: : 可以走到任意的叶子节点(不含0)，bob只能走到0，求出alice可能拿到的最大分数。
: :
: : 思路:
: : 1.bob只能走到0，所以我们可以先找出bob走到0的路径中，走到每个点花的时间，用dfs
: : 找就可以了，如果路径终点不为0，该点就标记成无限大。
: : 2.alice用dfs遍历所有点，如果这个点bob比你早走过你就拿不到分数，如果你们同时到
: : 就平分，如果你早到就全拿，当走到叶子节点的时候取最大的分数。
: :
: :
: 思路
: 一样
: 重点就是要知道bob有走过的地方
: 在那个地方他们两个人走了多远
: 就可以知道当前该0 1/2 或是1了
: 然后他们两个的dfs逻辑不太一样
: 所以分开来写
: 0.0
: 今天好麻烦