🔗 🔴 2065. Maximum Path Quality of a Graph 2178

tags: Weekly Contest 266 陣列(Array) 圖(Graph) 回溯(Backtracking)

題意

給定一個包含 nn 個節點的無向圖，節點編號從 00 到 n−1n-1 。給定一個下標從 00 開始的整數陣列 values\text{values}，其中 values[i]\text{values}[i] 表示第 ii 個節點的值。同時給定一個下標從 00 開始的二維整數陣列 edges\text{edges}，其中 edges[j]=[uj,vj,timej]\text{edges}[j] = [u_j, v_j, \text{time}_j] 表示節點 uju_j 和 vjv_j 之間有一條需要 timej\text{time}_j 秒才能通過的無向邊。最後，給定一個整數 maxTime\text{maxTime}。

有效路徑(valid path) 是指從節點 00 開始，回到節點 00，並且最多需要 maxTime\text{maxTime} 秒完成的任何路徑。可以 多次訪問 同一個節點。有效路徑的 品質(quality) 是路徑中訪問的唯一節點值的總和，即每個節點的值最多只加一次到總和中。

返回有效路徑的最大品質。

約束條件

  • 1≤n=values.length≤10001 \leq n = \text{values.length} \leq 1000
  • 0≤values[i]≤1080 \leq \text{values}[i] \leq 10^8
  • 0≤edges.length≤20000 \leq \text{edges.length} \leq 2000
  • edges[j].length=3\text{edges}[j].length = 3
  • 0≤uj<vj≤n−10 \leq u_j < v_j \leq n - 1
  • 10≤timej,maxTime≤10010 \leq \text{time}_j, \text{maxTime} \leq 100
  • [uj,vj][u_j, v_j] 所有節點對 互不相同。
  • 每個節點 至多有四條 邊。
  • 圖可能不連通。

思路：回溯(Backtracking)

注意到約束條件中的 10≤timej,maxTime≤10010 \leq \text{time}_j, \text{maxTime} \leq 100 ，可以知道在一條路徑中，最多只會經過 1010 條邊，且每個節點最多只有 44 條邊。因此可能的路徑數量最多只有 4104^{10} 種，可以使用 回溯(Backtracking) 來解決這個問題。

首先根據給定的 edges\text{edges} 來建立圖的 鄰接表(adjacency list) ，列表中的每個元素都是一個二元組，表示相鄰節點及其時間。

接著定義一個深搜函數 dfs(u,time,quality)dfs(u, \text{time}, \text{quality})，用來遍歷每條可能的路徑，其中 uu 表示當前節點，time\text{time} 表示移動到當前節點所需的總時間，quality\text{quality} 表示當前路徑的品質。使用一個全域變數 ansans 來記錄最大品質，並使用 visitedvisited 陣列來記錄當前節點是否已經訪問過。

  • 如果當前節點是 00，更新答案 ansans 為當前路徑品質和已有最大品質中的最大值。
  • 遍歷當前節點的所有相鄰節點 vv ，檢查移動到 vv 後的總時間是否超過最大時間 maxTimemaxTime ，如果超過則直接跳過。
  • 根據題意，一個邊可以走多次，但是節點的值只能加一次，因此需要標記節點是否已經訪問過。
    • 若已經訪問過 vv，則雖然可以繼續往下走，但是不會獲得 value，遞迴呼叫 dfs(v,time+t,quality)dfs(v, \text{time} + t, \text{quality})。
    • 若還沒訪問過 vv，可以獲得 value，設置訪問標記為已訪問，遞迴呼叫 dfs(v,time+t,quality+values[v])dfs(v, \text{time} + t, \text{quality} + \text{values}[v])。
      • 在遞迴前將下一個節點標記為已訪問，以便在遞迴過程中不會再次訪問此節點。但需要在返回上一步之前，重置訪問標記（恢復原狀），以便其他路徑能夠再次訪問此節點。

由於我們是在遞迴前將下一個節點標記為已訪問，因此在開始搜索之前，標記節點 00 為已訪問，並從節點 00 開始進行搜尋，即調用 dfs(0,0,values[0])dfs(0, 0, \text{values}[0])，最後返回答案 ansans 即可。

複雜度分析

  • 時間複雜度：O(n+m+4k)\mathcal{O}(n + m + 4^k)，其中 nn 是節點數，mm 是邊數，k=maxTimeminTimek = \frac{\text{maxTime}}{\text{minTime}}。
  • 空間複雜度：O(n+m+k)\mathcal{O}(n + m + k)，主要用於存儲圖的鄰接表及訪問標記陣列，以及遞迴時所需要的堆疊空間。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:
        n = len(values)
        g = [[] for _ in range(n)]
        for u, v, t in edges:
            g[u].append((v, t))
            g[v].append((u, t))

        ans = 0
        visited = [False] * n

        def dfs(u: int, time: int, quality: int) -> None:
            if u == 0: # 回到起點，但還可以繼續往下走，不用 return
                nonlocal ans
                ans = max(ans, quality)
            for v, t in g[u]:
                if time + t > maxTime:
                    continue
                if not visited[v]: # 沒有走過，可以獲得 value
                    visited[v] = True
                    dfs(v, time + t, quality + values[v])
                    visited[v] = False
                else: # 走過了，還是可以繼續往下走，但是不會獲得 value
                    dfs(v, time + t, quality)

        visited[0] = True
        dfs(0, 0, values[0])
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {
        int n = values.size();
        vector<vector<pair<int, int>>> g(n);
        for (auto& e : edges) {
            g[e[0]].emplace_back(e[1], e[2]);
            g[e[1]].emplace_back(e[0], e[2]);
        }

        int ans = 0;
        vector<bool> visited(n, false);
        function<void(int, int, int)> dfs = [&](int u, int time, int quality) {
            if (u == 0) ans = max(ans, quality);
            for (auto& [v, t] : g[u]) {
                if (time + t > maxTime) continue;
                if (!visited[v]) {
                    visited[v] = true;
                    dfs(v, time + t, quality + values[v]);
                    visited[v] = false;
                } else {
                    dfs(v, time + t, quality);
                }
            }
        };
        visited[0] = true;
        dfs(0, 0, values[0]);
        return ans;
    }
};

寫在最後

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail,
1 girl, solo, long hair, black hair, blue eyes, skirt, shirt, school uniform, standing, white shirt, short sleeves, pleated skirt, outdoors, sky, serafuku, (pink serafuku, pink school uniform), day, sailor collar, blurry, arm up, neckerchief, long skirt, girl