LeetCode题解(LCP16)：游乐园的游览计划(Python)_leecode 寻找最合适的景点路线

题目：原题链接（困难）

标签：图、数学

解法一：

class Solution:
    def maxWeight(self, edges: List[List[int]], value: List[int]) -> int:
        n = len(value)

        # 构造图
        graph = collections.defaultdict(set)
        for edge in edges:
            graph[edge[0]].add(edge[1])
            graph[edge[1]].add(edge[0])

        ans = 0

        # 遍历每个景点为重点景点A
        for a in range(n):
            # 计算所有可能的路径
            near = graph[a]
            path = []
            for j in near:
                for k in near:
                    if j < k and k in graph[j]:  # j < k -> 确保每条路径只被添加一次
                        path.append([j, k])

            # 计算最大的路径组合
            if len(path) == 0:
                continue
            elif len(path) == 1:
                b, c = path[0][0], path[0][1]
                ans = max(ans, value[a] + value[b] + value[c])
            else:
                for j1 in range(len(path)):
                    for j2 in range(j1 + 1, len(path)):
                        res = value[a]
                        for j in {path[j1][0], path[j1][1], path[j2][0], path[j2][1]}:
                            res += value[j]
                        ans = max(ans, res)

        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
31
32
33
34
35
36
37

解法二：

class Solution:
    def maxWeight(self, edges: List[List[int]], value: List[int]) -> int:
        # 生成无向图的邻接列表结构（每个点只记录比它下标大的邻边）
        graph = collections.defaultdict(set)
        for n1, n2 in edges:
            if n1 > n2:
                n1, n2 = n2, n1
            graph[n1].add(n2)

        # ---------- 寻找无向图中的三角形 ----------
        triangle_by_point_max = collections.defaultdict(list)  # 当前点构成的最大三角形（用于两个三角形完全重合的情况）
        triangle_by_point = collections.defaultdict(list)  # 当前点能构成的所有三角形
        triangle_by_edge = collections.defaultdict(list)  # 当前边能构成的前三大的三角形

        for i in range(len(value)):  # 遍历所有顶点
            for j in graph[i]:  # 遍历顶点的邻边的顶点（根据无向图的性质，有:i<j)
                for k in list(graph[i] & graph[j]):  # 遍历所有与i和j能构成三角形的点（根据无向图的性质，有:i<j<k)
                    # 计算并缓存三角形的喜爱度得分
                    triangle_mark = value[i] + value[j] + value[k]

                    triangle_info = [i, j, k, triangle_mark]

                    for n in [i, j, k]:  # 遍历三角形的3个顶点
                        # 更新三个三角形顶点构成的最大三角形
                        if not triangle_by_point_max[n] or triangle_by_point_max[n][-1] < triangle_mark:
                            triangle_by_point_max[n] = triangle_info

                        # 更新三个三角形顶点构成的所有三角形
                        triangle_by_point[n].append([i, j, k])

                    for edge in [(i, j), (i, k), (j, k)]:  # 遍历三角形的3条边
                        # 更新三角形三条边构成的前三大的三角形
                        triangle_by_edge[edge].append(triangle_info)
                        triangle_by_edge[edge].sort(key=lambda x: x[-1], reverse=True)
                        if len(triangle_by_edge[edge]) > 3:
                            triangle_by_edge[edge].pop()

        #  ---------- 拼接无向图中的三角形 ----------
        ans = 0

        for i in range(0, len(value)):  # 遍历所有顶点
            # 当前点没有三角形的情况
            if not triangle_by_point_max[i]:
                continue

            max_triangle = triangle_by_point_max[i]  # 当前顶点的最大三角形

            # 【三角形拼接的情况】
            # 已知△xab是包含x的最大三角形，不妨设以x为中心的最优解的两个三角形为△xpq和△xrt
            # 1. 如果a和b都不在pqrt中，那么直接将其中一个三角形换成△xab可获得更优解
            # 2. 如果a和b有一个在pqrt中，那么将对应的那个三角形换成△xab可获得更优解
            # 所以a和b一定同时在pqrt中，可能在一个三角形中，也可以不在也可以三角形中，于是得出以下3种情形：

            # [情形1]最大三角形△xab的两个顶点a和b在同一个三角形中，且当前点只有这一个三角形：两个三角形完全重合的情况
            ans = max(ans, max_triangle[-1])

            # [情形2]最大三角形△xab的两个顶点a和b在同一个三角形中，且当前点还有其他三角形：两个三角形共用一个顶点、一个邻边或重合
            for info in triangle_by_point[i]:
                ans = max(ans, sum(value[x] for x in set(max_triangle[:3]) | set(info[:3])))
                # ans = max(ans, self.count_val(max_triangle, info))

            # [情形3]最大三角形△xab的两个顶点a和b在不同三角形中（分别以a和b寻找三角形）：两个三角形共用一个顶点
            max_points = max_triangle[:3]
            max_points.remove(i)
            edge1, edge2 = [(i, x) if i < x else (x, i) for x in max_points]

            for info1 in triangle_by_edge[edge1]:
                for info2 in triangle_by_edge[edge2]:
                    ans = max(ans, sum(value[x] for x in set(info1[:3]) | set(info2[:3])))

        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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71