游乐园的游览计划

难度: Hard

又到了一年一度的春游时间，小吴计划去游乐场游玩 1 天，游乐场总共有 N 个游乐项目，编号从 0 到 N-1。小吴给每个游乐项目定义了一个非负整数值 value[i] 表示自己的喜爱值。两个游乐项目之间会有双向路径相连，整个游乐场总共有 M 条双向路径，保存在二维数组 edges中。小吴计划选择一个游乐项目 A 作为这一天游玩的重点项目。上午小吴准备游玩重点项目 A 以及与项目 A 相邻的两个项目 B、C （项目A、B与C要求是不同的项目，且项目B与项目C要求相邻），并返回 A ，即存在一条 A-B-C-A 的路径。下午，小吴决定再游玩重点项目 A以及与A相邻的两个项目 B'、C'，（项目A、B'与C'要求是不同的项目，且项目B'与项目C'要求相邻），并返回 A ，即存在一条 A-B'-C'-A 的路径。下午游玩项目 B'、C' 可与上午游玩项目B、C存在重复项目。小吴希望提前安排好游玩路径，使得喜爱值之和最大。请你返回满足游玩路径选取条件的最大喜爱值之和，如果没有这样的路径，返回 0。注意：一天中重复游玩同一个项目并不能重复增加喜爱值了。例如：上下午游玩路径分别是 A-B-C-A与A-C-D-A 那么只能获得 value[A] + value[B] + value[C] + value[D] 的总和。

示例 1：

输入：edges = [[0,1],[1,2],[0,2]], value = [1,2,3]

输出：6

解释：喜爱值之和最高的方案之一是 0->1->2->0 与 0->2->1->0 。重复游玩同一点不重复计入喜爱值，返回1+2+3=6

示例 2：

输入：edges = [[0,2],[2,1]], value = [1,2,5]

输出：0

解释：无满足要求的游玩路径，返回 0

示例 3：

输入：edges = [[0,1],[0,2],[0,3],[0,4],[0,5],[1,3],[2,4],[2,5],[3,4],[3,5],[4,5]], value = [7,8,6,8,9,7]

输出：39

解释：喜爱值之和最高的方案之一是 3->0->1->3 与 3->4->5->3 。喜爱值最高为 7+8+8+9+7=39

限制：

3 <= value.length <= 10000
1 <= edges.length <= 10000
0 <= edges[i][0],edges[i][1] < value.length
0 <= value[i] <= 10000
edges中没有重复的边
edges[i][0] != edges[i][1]

Submission

运行时间: 707 ms

内存: 70.6 MB

from sortedcontainers import SortedList


def minmax(u, v):
    return (u, v) if u < v else (v, u)


class Solution:
    def maxWeight(self, edges: List[List[int]], val: List[int]) -> int:
        n = len(val)
        deg, g = [0] * n, [[] for _ in range(n)]
        for u, v in edges:
            deg[u] += 1
            deg[v] += 1
        for u, v in edges:
            if (deg[u], u) > (deg[v], v):
                u, v = v, u
            g[u].append(v)
        ans = 0
        triple = [[] for _ in range(n)]
        vis = [0] * n
        for u in range(n):
            for v in g[u]:
                vis[v] = 1
            for v in g[u]:
                for k in g[v]:
                    if vis[k]:
                        ans = max(ans, val[u] + val[v] + val[k])
                        triple[u].append(minmax(v, k))
                        triple[v].append(minmax(u, k))
                        triple[k].append(minmax(u, v))
            for v in g[u]:
                vis[v] = 0
        for p, ll in enumerate(triple):
            ll.sort()
            stack = []
            for u, k in ll:
                if len(stack) <= 4:
                    heapq.heappush(stack, (val[u] + val[k], u, k))
                else:
                    heapq.heappush(stack, (val[u] + val[k], u, k))
                    heapq.heappop(stack)
            n = len(stack)
            for i in range(n):
                c = set()
                c.add(stack[i][1])
                c.add(stack[i][2])
                for j in range(i + 1, n):
                    if stack[j][1] in c:
                        ans = max(
                            ans, val[stack[i][1]] + val[stack[i][2]] + val[stack[j][2]]
                        )
                    elif stack[j][2] in c:
                        ans = max(
                            ans,
                            val[stack[i][1]]
                            + val[stack[i][2]]
                            + val[stack[j][1]]
                            + val[p],
                        )
                    else:
                        ans = max(
                            ans,
                            val[stack[i][1]]
                            + val[stack[i][2]]
                            + val[stack[j][1]]
                            + val[stack[j][2]]
                            + val[p],
                        )
        return ans

Explain

题解的核心思想是通过构建图的邻接表来快速查找节点的相邻节点，从而高效地找到可能的A-B-C-A形式的游玩路径。首先，它通过统计每个节点的度和构建邻接表来初始化图结构。然后，通过对每个节点作为A尝试找到B和C，使得存在A-B-C-A的路径，并记录这样的三元组。对于每个节点，使用一个排序列表来保持值最大的几个B-C对。这样，在最后的步骤中，可以高效地检查和计算所有可能的A-B-C-A和A-B'-C'-A组合的最大喜爱值总和。

时间复杂度: O(N*d^2 + M)

空间复杂度: O(N + M)

from sortedcontainers import SortedList


def minmax(u, v):
    return (u, v) if u < v else (v, u)


class Solution:
    def maxWeight(self, edges: List[List[int]], val: List[int]) -> int:
        n = len(val)
        deg, g = [0] * n, [[] for _ in range(n)]
        for u, v in edges:  # 构建邻接表
            deg[u] += 1  # 计算每个点的度
            deg[v] += 1
        for u, v in edges:  # 优化建图，使得度小的点指向度大的点
            if (deg[u], u) > (deg[v], v):
                u, v = v, u
            g[u].append(v)
        ans = 0
        triple = [[] for _ in range(n)]  # 存储每个节点可能的B-C对
        vis = [0] * n  # 访问数组，用于检查节点是否被访问过
        for u in range(n):
            for v in g[u]:
                vis[v] = 1
            for v in g[u]:
                for k in g[v]:  # 遍历所有可能的B-C对
                    if vis[k]:  # 检查C是否已访问，确保路径合法
                        ans = max(ans, val[u] + val[v] + val[k])  # 更新最大喜爱值
                        triple[u].append(minmax(v, k))  # 存储三元组
                        triple[v].append(minmax(u, k))
                        triple[k].append(minmax(u, v))
            for v in g[u]:
                vis[v] = 0  # 清除访问标记
        for p, ll in enumerate(triple):  # 对每个节点处理可能的路径组合
            ll.sort()  # 对三元组排序
            stack = []  # 使用堆维护最大的B-C对
            for u, k in ll:
                if len(stack) <= 4:
                    heapq.heappush(stack, (val[u] + val[k], u, k))
                else:
                    heapq.heappush(stack, (val[u] + val[k], u, k))
                    heapq.heappop(stack)  # 保持堆的大小为最大的4个
            n = len(stack)
            for i in range(n):
                c = set()
                c.add(stack[i][1])
                c.add(stack[i][2])
                for j in range(i + 1, n):  # 计算两个路径的组合是否有效
                    if stack[j][1] in c:
                        ans = max(
                            ans, val[stack[i][1]] + val[stack[i][2]] + val[stack[j][2]]
                        )
                    elif stack[j][2] in c:
                        ans = max(
                            ans,
                            val[stack[i][1]] + val[stack[i][2]] + val[stack[j][1]] + val[p],
                        )
                    else:
                        ans = max(
                            ans,
                            val[stack[i][1]] + val[stack[i][2]] + val[stack[j][1]] + val[stack[j][2]] + val[p],
                        )
        return ans  # 返回计算的最大喜爱值

Explore

这种策略主要是为了减少在图遍历过程中的冗余操作，特别是在寻找A-B-C-A型路径时。具体来说，当一个度数较小的节点指向一个度数较大的节点时，可以减少遍历的次数，因为较小度数的节点作为出发点时，其连接的选项较少，从而减少了需要检查的路径数量。这样，每次从一个度数较小的节点开始遍历，只需要较少的操作就可以检查到其所有相邻的较高度数节点。这不仅提高了算法的效率，也减少了无效的计算，尤其是在图较为稠密时，此策略能显著减少计算量。

在算法中，通过维护一个访问数组`vis`来跟踪哪些节点已经被作为B访问过，可以有效避免在找C时重复选择相同的B。当遍历到节点A的邻接节点B时，将B标记为已访问。接着在找C时只考虑那些未被标记的节点，这样就可以确保B和C不会与A相同，也避免了B和C的重复。每次完成A的B-C对探索后，需要重置访问数组，以便于下一个节点的探索不会受到影响。

确实，如果节点A的邻接节点数量很少，这将直接影响找到有效的B-C对的概率，因为可选的B和C较少，可能无法形成有效的A-B-C-A路径。在这种情况下，虽然不能改变图的结构，但可以通过算法逻辑优化来尽量提高查找效率。例如，可以专门对那些度数较小的节点进行优化处理，如在找到一个有效的B-C对后立即中断当前搜索，减少无效的计算。同时，也可以通过预处理和缓存一些结果来加速对这类节点的查询。