Re: [閒聊] 每日leetcode
※ 引述 《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
今天好麻煩
```cpp
class Solution {
public:
vector<int> passed;
vector<int> bobpassed;
unordered_map<int,int> bobmap;
unordered_map<int,vector<int>> path;
vector<int> amounts;
int res;
void bob(int now , int dist , vector<int>& sb)
{
sb.push_back(now);
if(now == 0)
{
for(int i = 0 ; i < sb.size() ; i ++)
{
bobmap[sb[i]] = i+1;
}
return ;
}
for(int nxt : path[now] )
{
if(bobpassed[nxt] == 1)continue;
bobpassed[nxt] = 1;
bob(nxt , dist+1 , sb);
}
sb.pop_back();
}
void alice(int now , int dist , int money)
{
if(bobmap[now] == dist)
{
money += amounts[now]/2;
}
else if(bobpassed[now] == 1 && bobmap[now] < dist)
{
}
else
{
money += amounts[now];
}
// cout << now << " " << money << " " << dist << endl;
if(path[now].size() == 1 && now != 0)
{
res = max(res,money);
return;
}
for(int nxt : path[now])
{
if(passed[nxt] == 1)continue;
passed[nxt] = 1;
alice(nxt , dist+1 , money);
}
}
int mostProfitablePath(vector<vector<int>>& edges, int bobh, vector<int>& am
ount)
{
res = INT_MIN;
int n = edges.size();
amounts = amount;
passed.resize(n+1,0);
bobpassed.resize(n+1,INT_MAX);
for(int i = 0 ; i <= n ; i ++)
{
bobmap[i] = INT_MAX;
}
for(int i = 0 ; i < n ; i ++)
{
path[edges[i][0]].push_back(edges[i][1]);
path[edges[i][1]].push_back(edges[i][0]);
}
vector<int> hi;
bobpassed[bobh] = 1;
bob(bobh , 1 , hi );
passed[0] = 1;
alice(0,1,0);
return res;
}
};
```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 134.208.244.226 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1740417162.A.6F5.html
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 1346 之 1552 篇)：