Re: [閒聊] 每日leetcode

看板Marginalman作者sixB (6B)時間9月前 (2025/02/25 01:30)推噓0(0推 0噓 1→)

思路不一樣怎麼大家都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 : 今天好麻煩 -- 很姆的咪姆之咪 http://i.imgur.com/5sw7QOj.jpg