节点序列的最大得分

标签: 图 数组 枚举 排序

难度: Hard

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

给你一个下标从 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 * 104
  • 1 <= scores[i] <= 108
  • 0 <= edges.length <= 5 * 104
  • edges[i].length == 2
  • 0 <= ai, bi <= n - 1
  • ai != bi
  • 不会有重边。

Submission

运行时间: 283 ms

内存: 34.8 MB

class Solution:
    def maximumScore(self, scores: List[int], edges: List[List[int]]) -> int:
        n = len(scores)
        scores.append(-inf)
        arr = [[n]*3 for _ in range(n)]
        for a, b in edges:
            sa, sb = scores[a], scores[b]
            if scores[a] > scores[arr[b][0]]:
                arr[b][2], arr[b][1], arr[b][0] = arr[b][1], arr[b][0], a
            elif scores[a] > scores[arr[b][1]]:
                arr[b][2], arr[b][1] = arr[b][1], a
            elif scores[a] > scores[arr[b][2]]:
                arr[b][2] = a 
            if scores[b] > scores[arr[a][0]]:
                arr[a][2], arr[a][1], arr[a][0] = arr[a][1], arr[a][0], b
            elif scores[b] > scores[arr[a][1]]:
                arr[a][2], arr[a][1] = arr[a][1], b
            elif scores[b] > scores[arr[a][2]]:
                arr[a][2] = b
        res = -1
        for a, b in edges:
            temp = scores[a] + scores[b]
            if arr[a][0] != b:
                c = arr[a][0]
                temp += scores[c]
            else:
                c = arr[a][1]
                temp += scores[c]
            if arr[b][0] != a and arr[b][0] != c:
                temp += scores[arr[b][0]]
            elif arr[b][1] != a and arr[b][1] != c:
                temp += scores[arr[b][1]]
            else:
                temp += scores[arr[b][2]]
            if temp > res:
                res = temp
            temp = scores[a] + scores[b]
            if arr[b][0] != a:
                c = arr[b][0]
                temp += scores[c]
            else:
                c = arr[b][1]
                temp += scores[c]
            if arr[a][0] != b and arr[a][0] != c:
                temp += scores[arr[a][0]]
            elif arr[a][1] != b and arr[a][1] != c:
                temp += scores[arr[a][1]]
            else:
                temp += scores[arr[a][2]]
            if temp > res:
                res = temp
        return res

Explain

该题解的思路如下： 1. 为每个节点维护一个长度为3的数组，存储与该节点相连的分数最高的3个节点。 2. 遍历所有边，更新每个节点的相连节点数组。 3. 再次遍历所有边，对于每条边(a,b)，尝试以a和b为中心节点构造长度为4的节点序列，选取a和b各自相连的最高分节点作为端点，计算序列得分。 4. 在所有可能的节点序列中，选取得分最高的作为最终答案。

时间复杂度: O(m)

空间复杂度: O(n)

class Solution:
    def maximumScore(self, scores: List[int], edges: List[List[int]]) -> int:
        n = len(scores)
        scores.append(-inf)  # 添加一个虚拟节点，分数为负无穷
        # 初始化每个节点相连的最高分节点数组
        arr = [[n]*3 for _ in range(n)]
        # 遍历所有边，更新相连节点数组
        for a, b in edges:
            sa, sb = scores[a], scores[b]
            # 更新节点b的相连节点数组
            if scores[a] > scores[arr[b][0]]:
                arr[b][2], arr[b][1], arr[b][0] = arr[b][1], arr[b][0], a
            elif scores[a] > scores[arr[b][1]]:
                arr[b][2], arr[b][1] = arr[b][1], a
            elif scores[a] > scores[arr[b][2]]:
                arr[b][2] = a 
            # 更新节点a的相连节点数组
            if scores[b] > scores[arr[a][0]]:
                arr[a][2], arr[a][1], arr[a][0] = arr[a][1], arr[a][0], b
            elif scores[b] > scores[arr[a][1]]:
                arr[a][2], arr[a][1] = arr[a][1], b
            elif scores[b] > scores[arr[a][2]]:
                arr[a][2] = b
        res = -1
        # 再次遍历所有边，构造节点序列并计算得分
        for a, b in edges:
            # 以a为中心节点构造序列
            temp = scores[a] + scores[b]
            if arr[a][0] != b:
                c = arr[a][0]
                temp += scores[c]
            else:
                c = arr[a][1]
                temp += scores[c]
            if arr[b][0] != a and arr[b][0] != c:
                temp += scores[arr[b][0]]
            elif arr[b][1] != a and arr[b][1] != c:
                temp += scores[arr[b][1]]
            else:
                temp += scores[arr[b][2]]
            res = max(res, temp)
            # 以b为中心节点构造序列
            temp = scores[a] + scores[b]
            if arr[b][0] != a:
                c = arr[b][0]
                temp += scores[c]
            else:
                c = arr[b][1]
                temp += scores[c]
            if arr[a][0] != b and arr[a][0] != c:
                temp += scores[arr[a][0]]
            elif arr[a][1] != b and arr[a][1] != c:
                temp += scores[arr[a][1]]
            else:
                temp += scores[arr[a][2]]
            res = max(res, temp)
        return res

Explore

在这种情况下，我们会使用一个虚拟节点来填充数组中剩余的位置，这个虚拟节点的分数设为负无穷（-inf），这样就不会影响到最大分值的计算。在实际代码实现中，这通常表示这些位置是无效的或者不存在实际的节点。

题解中的算法没有明确指出如何处理分数相同的情况。通常，这类情况可以根据节点的序号或者先遍历到的顺序来进行决定。实际应用中可以根据具体需求来定制排序的规则。例如，可以简单地按照节点编号的升序或降序来进行存储。

使用贪心策略并不能保证总是得到最大得分的四节点序列。贪心策略仅保证在当前选择中是最优的，但可能错过了由于节点间相互依赖而导致的全局最优解。例如，可能存在一种情况，选择次优的节点作为序列的一部分，会与其他节点组合产生更高的总得分。

题解中通过检查节点是否已经被使用来避免重复。具体来说，当尝试构建以节点a和节点b为中心的序列时，代码会检查a和b的最高分节点是否与对方或已选择的节点重复。如果发现重复，算法会选择下一个最高分的节点。这样的处理确保了每个节点只在序列中出现一次，避免了重复计分的问题。