Hard

题目描述

给你一个有 n 个节点的无向图，节点编号从 0 到 n - 1。

给你一个长度为 n 的下标从 0 开始的整数数组 scores，其中 scores[i] 表示节点 i 的分数。同时给你一个二维整数数组 edges，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间存在一条无向边。

如果一个节点序列满足以下条件，我们称它是 有效的：

  • 序列中每对相邻节点之间都存在一条边。
  • 序列中没有节点出现超过一次。

节点序列的得分定义为序列中所有节点得分的总和。

请你返回长度为 4 的有效节点序列的最大得分。如果不存在这样的序列，请返回 -1。

示例 1：

输入：scores = [5,2,9,8,4], edges = [[0,1],[1,2],[2,3],[0,2],[1,3],[2,4]]
输出：24
解释：上图展示了图和选择的节点序列 [0,1,2,3]。
节点序列的得分为 5 + 2 + 9 + 8 = 24。
可以证明没有其他节点序列的得分超过 24。
注意序列 [3,1,2,0] 和 [1,0,2,3] 也是有效的，得分为 24。
序列 [0,3,2,4] 无效，因为节点 0 和 3 之间没有边。

示例 2：

输入：scores = [9,20,6,4,11,12], edges = [[0,3],[5,3],[2,4],[1,3]]
输出：-1
解释：上图展示了图。
不存在长度为 4 的有效节点序列，所以返回 -1。

提示：

  • n == scores.length
  • 4 <= n <= 5 * 10^4
  • 1 <= scores[i] <= 10^8
  • 0 <= edges.length <= 5 * 10^4
  • edges[i].length == 2
  • 0 <= ai, bi <= n - 1
  • ai != bi
  • 没有重复的边。

解题思路

这道题要求找到长度为4的节点序列，使得相邻节点都有边连接，且节点得分和最大。

核心思路： 长度为4的路径可以表示为 a-b-c-d，其中 b 和 c 是中间的两个节点。我们可以枚举所有可能的中间边 (b,c)，然后为每个这样的边找到最优的端点 a 和 d。

算法步骤：

  1. 预处理邻接表：对于每个节点，保存与它相邻且得分最高的前3个节点。为什么是3个？因为在选择端点时，可能会遇到节点重复的情况，需要有备选方案。

  2. 枚举中间边：遍历所有边作为中间边 (b,c)。

  3. 选择最优端点：

    • 从节点 b 的邻居中选择得分最高的节点作为 a
    • 从节点 c 的邻居中选择得分最高的节点作为 d
    • 确保 a、b、c、d 四个节点互不相同

  4. 维护最大得分：在所有有效的4节点路径中找到得分最大值。

优化关键点：

  • 每个节点只保存前3个最高得分的邻居，大大减少搜索空间
  • 通过枚举中间边而不是暴力枚举所有4节点组合，将复杂度从 O(n^4) 降到 O(E)

时间复杂度为 O(E + V log V)，其中排序邻居列表需要 O(V log V)，枚举边和查找最优解需要 O(E)。

代码实现

class Solution {
public:
    int maximumScore(vector<int>& scores, vector<vector<int>>& edges) {
        int n = scores.size();
        vector<vector<int>> adj(n);
        
        // 构建邻接表
        for (auto& edge : edges) {
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
        
        // 对每个节点的邻居按得分排序，只保留前3个
        for (int i = 0; i < n; i++) {
            sort(adj[i].begin(), adj[i].end(), [&](int a, int b) {
                return scores[a] > scores[b];
            });
            if (adj[i].size() > 3) {
                adj[i].resize(3);
            }
        }
        
        int maxScore = -1;
        
        // 枚举所有边作为中间边
        for (auto& edge : edges) {
            int b = edge[0], c = edge[1];
            
            // 尝试所有可能的a和d组合
            for (int a : adj[b]) {
                if (a == c) continue;
                for (int d : adj[c]) {
                    if (d == b || d == a) continue;
                    maxScore = max(maxScore, scores[a] + scores[b] + scores[c] + scores[d]);
                }
            }
        }
        
        return maxScore;
    }
};

class Solution:
    def maximumScore(self, scores: List[int], edges: List[List[int]]) -> int:
        n = len(scores)
        adj = [[] for _ in range(n)]
        
        # 构建邻接表
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
        
        # 对每个节点的邻居按得分排序，只保留前3个
        for i in range(n):
            adj[i].sort(key=lambda x: scores[x], reverse=True)
            adj[i] = adj[i][:3]
        
        max_score = -1
        
        # 枚举所有边作为中间边
        for b, c in edges:
            # 尝试所有可能的a和d组合
            for a in adj[b]:
                if a == c:
                    continue
                for d in adj[c]:
                    if d == b or d == a:
                        continue
                    max_score = max(max_score, scores[a] + scores[b] + scores[c] + scores[d])
        
        return max_score

public class Solution {
    public int MaximumScore(int[] scores, int[][] edges) {
        int n = scores.Length;
        List<int>[] adj = new List<int>[n];
        
        // 初始化邻接表
        for (int i = 0; i < n; i++) {
            adj[i] = new List<int>();
        }
        
        // 构建邻接表
        foreach (var edge in edges) {
            adj[edge[0]].Add(edge[1]);
            adj[edge[1]].Add(edge[0]);
        }
        
        // 对每个节点的邻居按得分排序，只保留前3个
        for (int i = 0; i < n; i++) {
            adj[i].Sort((a, b) => scores[b].CompareTo(scores[a]));
            if (adj[i].Count > 3) {
                adj[i] = adj[i].Take(3).ToList();
            }
        }
        
        int maxScore = -1;
        
        // 枚举所有边作为中间边
        foreach (var edge in edges) {
            int b = edge[0], c = edge[1];
            
            // 尝试所有可能的a和d组合
            foreach (int a in adj[b]) {
                if (a == c) continue;
                foreach (int d in adj[c]) {
                    if (d == b || d == a) continue;
                    maxScore = Math.Max(maxScore, scores[a] + scores[b] + scores[c] + scores[d]);
                }
            }
        }
        
        return maxScore;
    }
}

var maximumScore = function(scores, edges) {
    const n = scores.length;
    const adj = Array(n).fill().map(() => []);
    
    // Build adjacency list
    for (const [u, v] of edges) {
        adj[u].push(v);
        adj[v].push(u);
    }
    
    // For each node, keep only top 3 neighbors by score
    for (let i = 0; i < n; i++) {
        adj[i].sort((a, b) => scores[b] - scores[a]);
        if (adj[i].length > 3) {
            adj[i] = adj[i].slice(0, 3);
        }
    }
    
    let maxScore = -1;
    
    // Try all edges as the middle edge
    for (const [u, v] of edges) {
        // u and v are the middle two nodes
        // Try all combinations of their neighbors
        for (const x of adj[u]) {
            if (x === v) continue;
            for (const y of adj[v]) {
                if (y === u || y === x) continue;
                const score = scores[x] + scores[u] + scores[v] + scores[y];
                maxScore = Math.max(maxScore, score);
            }
        }
    }
    
    return maxScore;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(V log V + E)
空间复杂度O(V + E)

其中 V 是节点数，E 是边数。时间复杂度中，O(V log V) 来自对每个节点的邻居排序，O(E) 来自枚举所有边。空间复杂度主要用于存储邻接表。

相关题目