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比你早走過你就拿不到分數，如果你們同時到
就平分，如果你早到就全拿，當走到葉子節點的時候取最大的分數。
Java Code:
---------------------------------------------------
class Solution {
private Map<Integer, List<Integer>> graph;
private int[] bobReachTime;
private int[] amount;
private int res;
public int mostProfitablePath(int[][] edges, int bob, int[] amount) {
int n = edges.length + 1;
this.amount = amount;
this.res = Integer.MIN_VALUE;
// 建圖
this.graph = new HashMap<>();
for (int i = 0; i < n; i++) {
this.graph.put(i, new ArrayList<>());
}
for (int[] edge : edges) {
graph.get(edge[0]).add(edge[1]);
graph.get(edge[1]).add(edge[0]);
}
// 計算bob到達每個點的時間
bobReachTime = new int[n];
Arrays.fill(bobReachTime, Integer.MAX_VALUE);
dfs1(bob, -1, 0);
// 計算alice成本
dfs2(0, -1, 0, 0);
return res;
}
private boolean dfs1(int curr, int prev, int t) {
if (curr == 0) {
bobReachTime[0] = t;
return true;
}
boolean canReachZero = false;
for (int next : graph.get(curr)) {
if (next == prev) {
continue;
}
if (dfs1(next, curr, t + 1)) {
canReachZero = true;
}
}
if (canReachZero) {
bobReachTime[curr] = t;
}
return canReachZero;
}
private void dfs2(int curr, int prev, int t, int income) {
if (t == bobReachTime[curr]) {
income += amount[curr]/2;
} else if (t < bobReachTime[curr]) {
income += amount[curr];
}
// 葉子節點且不為起點
if (graph.get(curr).size() == 1 && curr != 0) {
res = Math.max(res, income);
return;
}
for (int next : graph.get(curr)) {
if (next == prev) {
continue;
}
dfs2(next, curr, t + 1, income);
}
}
}
---------------------------------------------------
--
https://i.imgur.com/5xKbxoh.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.158.101.161 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1740400494.A.530.html