思路
不一樣
怎麼大家都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
: 今天好麻煩