LCP 16-游乐园的游览计划

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

又到了一年一度的春游时间，小吴计划去游乐场游玩 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]

题意概述：

在图中找到两个三角形（边可以重复），两个三角形至少需要一个点相连，使得最终所有点的权值和最大。

考点一：找三角形

我们知道点数和边数是一个数量级，这里我们就用 N 统一代替，三角形最多有 N\sqrt{N 个，如何遍历他们呢？

  • 假如某个顶点 v 的度数没有超过 \sqrt{N，枚举和 v 相邻的两个顶点，并用哈希表查看这两个顶点是否相连。所有这类点的处理复杂度为：\sum_v deg(v)^2 \leq \sum_v deg(v)\times\sqrt{N} = \sqrt{N} \times M = N\sqrt{N。
  • 对于剩下所有度数超过 \sqrt{N 的点，这类点的个数最多有 \sqrt{N 个，这是因为所有点度数之和等于 2M。那么对于这些点，枚举任意三个并利用哈希表查看是否有边相连。所有这类点的处理复杂度为：\sqrt{N}^3=N\sqrt{N。

对于一个三角形，如果有某一个顶点度数小于等于 \sqrt{N，可以通过第一种办法得到。如果所有点度数都超过 \sqrt{N，那么第二种方法可以找到。所以能够找到所有的三角形。注意这里两条边的查询一定要用 O(1) 的哈希表，而不能使用 O(\log N) 的二叉树，不然复杂度会多一个 \log。

考点二：三角形拼接

三角形的拼接有三种可能：

  1. 两个三角形完全重合
  2. 两个三角形重合一条边
  3. 两个三角形重合一条点
    对于第一种可能，我们找所有三角形时记录最大三角形的值；对于第二种可能，通过枚举一条边，计算第一和第二大三角形的和；我们重点讨论最后一种可能的求解方案，首先有下列性质。

性质：枚举一个点 x 作为两个三角形的重合点，假设它构成的最大三角形是 \triangle xab；那么另两个点 a、b 都出现在点 x 作为两个三角形重合点的最佳方案中

证明过程：
三角形 \triangle xab 是包含点 x 的最大三角形，考虑最优解是以 x 为中心点的两个三角形 \triangle xpq 和 \triangle xrt

  • 如果点 a 和 b 都不出现在 pqrt 中，那么直接将其中一个三角形换成 \triangle xab 可以得到更优解
  • 如果点 a 和 b 只有一个出现在 pqrt 中，那么将对应的那个三角形换成 \triangle xab 可以得到最优解
    所以点 a 和 b 一定同时出现在点 x 作为两个三角形重合点的最佳方案 pqrt 中

这里最佳方案中点 a 和 b 同时出现分两种情况讨论：

  • 如果点 a 和 b 出现在一个三角形中，那么直接用 \triangle xab 和另一个和 x 相邻的三角形一一组合
  • 如果点 a 和 b 不在一个三角形中，那么一定是 xa 这条边构成的三角形 + xb 这条边构成的三角形。这种情况，记录两条边出现的权值最大的三个三角形，然后一一尝试拼接即可。（这里记录Top3是因为Top2三角形可能存在重复的点）

综上，就变成枚举中间点 x，包含点 x 的最大三角形 \triangle xab 和所有包含 x 的三角形一一组合，以及包含边 xa 和边 xb 的最大的三个三角形一一组合，计算最终结果。（也可以推导出点 x 的 Top2 三角形 和所有包含 x 的三角形一一组合，证明方法类似）

[]
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
class Solution {
private:
    const static int MaxN = 20000 + 7;

    struct nodetype {
        int val, nod[3];
        bool equal(nodetype a) {
            return (val == a.val  nod[0] == a.nod[0]  nod[1] == a.nod[1]  nod[2] == a.nod[2]);
        }
    };

    vector<int> iv[MaxN], edgeid[MaxN];
    vector<int> weights;
    vector<nodetype> triangle[MaxN];
    nodetype tri[MaxN][4] = {0};
    unordered_map<int, int> link;
    vector<int> big;
    bool flg[MaxN] = {false};

    void Upload(int x, nodetype temp) {
        //更新编号为 x 的边的权值 Top3 的三角形
        int i;
        for (int i=0; i<3; ++i) {
            if (temp.equal(tri[x][i])) {
                return;
            }
        }
        for (i=2; i>=0; --i) {
            if (tri[x][i].val >= temp.val) {
                break;
            }
            tri[x][i+1] = tri[x][i];
        }
        tri[x][i+1] = temp;
    }

    void Update(int w, int a, int b, int c, int i, int j, int k) {
        // 点 i、j、k 以及 边的编号 a、b、c 的权值为 w
        // 记录三角形的信息和更新状态
        if (i > j) swap(i, j);
        if (i > k) swap(i, k);
        if (j > k) swap(j, k);
        nodetype temp;
        temp.val = w;
        temp.nod[0] = i;
        temp.nod[1] = j;
        temp.nod[2] = k;

        triangle[i].push_back(temp);
        triangle[j].push_back(temp);
        triangle[k].push_back(temp);

        Upload(a, temp);
        Upload(b, temp);
        Upload(c, temp);
    }
    int Combine(nodetype a, nodetype b) {
        // 计算两个三角形的返回值
        if (a.val == 0 || b.val == 0) return 0;
        int count = a.val;
        if (b.nod[0] != a.nod[0]  b.nod[0] != a.nod[1]  b.nod[0] != a.nod[2]) count += weights[b.nod[0]];
        if (b.nod[1] != a.nod[0]  b.nod[1] != a.nod[1]  b.nod[1] != a.nod[2]) count += weights[b.nod[1]];
        if (b.nod[2] != a.nod[0]  b.nod[2] != a.nod[1]  b.nod[2] != a.nod[2]) count += weights[b.nod[2]];
        return count;
    }

public:
    int maxWeight(vector< vector<int> > edges, vector<int> weight) {
        int n = weight.size();
        int m = edges.size();
        // 初始化
        for (int i=0; i<n; ++i) {
            weights.push_back(weight[i]);
            iv[i].clear();
            edgeid[i].clear();
        }
        for (int i=0; i<m; ++i) {
            triangle[i].clear();
        }
        big.clear();
        link.clear();

        // 记录映射关系
        for (int i=0; i<m; ++i) {
            // 点 与 点 的相连关系
            iv[edges[i][0]].push_back(edges[i][1]);   
            iv[edges[i][1]].push_back(edges[i][0]);
            // 点 与 边的编号 的关系
            edgeid[edges[i][0]].push_back(i);
            edgeid[edges[i][1]].push_back(i);
            // 两个点 对应的边的编号
            link[edges[i][0] * n + edges[i][1]] = i;
            link[edges[i][1] * n + edges[i][0]] = i;
        }

        int deg = sqrt(m);
        // 查找度数少的顶点 i 构成的所有三角形
        for (int i=0; i<n; ++i) {
            if (iv[i].size() < deg) {
                for (int j=0; j<iv[i].size(); ++j) {
                    for (int k=j+1; k<iv[i].size(); ++k) {
                        if (link.find(iv[i][j] * n + iv[i][k]) != link.end()) {
                            int jk = link[iv[i][j] * n + iv[i][k]];
                            Update(weight[i] + weight[iv[i][j]] + weight[iv[i][k]], edgeid[i][j], edgeid[i][k], jk, i, iv[i][j], iv[i][k]);
                        }
                    }
                }
            } else {
                big.push_back(i);
            }
        }
        // 查找度数多的顶点 i 构成的所有三角形
        for (int i=0; i<big.size(); ++i) {
            for (int j=i+1; j<big.size(); ++j) {
                for (int k=j+1; k<big.size(); ++k) {
                    if (link.find(big[i] * n + big[j]) != link.end()  link.find(big[i] * n + big[k]) != link.end()  link.find(big[j] * n + big[k]) != link.end()) {
                        int ij = link[big[i] * n + big[j]];
                        int ik = link[big[i] * n + big[k]];
                        int jk = link[big[j] * n + big[k]];
                        Update(weight[big[i]] + weight[big[j]] + weight[big[k]], ij, ik, jk, big[i], big[j], big[k]);
                    }
                }
            }
        }

        int ans = 0, count;

        for (int i=0; i<m; ++i) {
            if (tri[i][0].val != 0) {
                // 两个三角形完全重合的情况，即一个三角形
                ans = max(ans, tri[i][0].val); 
                if (tri[i][1].val != 0) {
                    // 两个三角形重合一条边
                    ans = max(ans, tri[i][0].val + tri[i][1].val - weight[edges[i][0]] - weight[edges[i][1]]); 
                }
            }
        }
        // 枚举中间点 i
        for (int i=0; i<n; ++i) {
            if (iv[i].size() == 0) continue;
            int maxline = edgeid[i][0];  // 最大三角形
            for (int j=1; j<edgeid[i].size(); ++j) {
                if (tri[maxline][0].val < tri[edgeid[i][j]][0].val) {
                    maxline = edgeid[i][j];
                }
            }
            int p, q, r;
            p = tri[maxline][0].nod[0];
            q = tri[maxline][0].nod[1];
            r = tri[maxline][0].nod[2];
            if (q == i) swap(q, p);
            if (r == i) swap(r, p);

            // 最大三角形 maxline 和所有包含 i 的三角形一一组合
            for (int j=0; j<triangle[i].size(); ++j) {
                ans = max(ans, Combine(tri[maxline][0], triangle[i][j]));
            }

            int l1, l2; 
            l1 = link[p * n + q];
            l2 = link[p * n + r];
            // 边 pq 和边 pr 的最大的三个三角形一一组合
            // 由于两边最大三角形都为 maxline, 前面已经讨论了，故不需要在这讨论最大三角形的组合
            ans = max(ans, Combine(tri[l1][1], tri[l2][1]));
            ans = max(ans, Combine(tri[l1][1], tri[l2][2]));
            ans = max(ans, Combine(tri[l1][2], tri[l2][1]));
        }

        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
72
73
import collections
class Solution:
    def maxWeight(self, edges: List[List[int]], weight: List[int]) -> int:
        n = len(weight)
        self.weight = weight
        point_set = collections.defaultdict(set) # 记录和 i相连且编号大于i的所有点
        for x,y in edges:
            if x>y:
                x,y = y,x
            point_set[x].add(y)

        max_triangle_point_dict = collections.defaultdict(list)  # 点i能构成的最大三角形
        triangle_point_dict = collections.defaultdict(list) # 点i能构成的所有三角形
        triangle_edge_dict = collections.defaultdict(list)  # 边(i,j)能构成的 Top3 三角形

        # 查找三角形
        for i in range(0,n):
            for j in point_set[i]:
                all_points_list = list(point_set[i]&point_set[j]) # 能与 i,j 构成三角形的点
                for k in all_points_list:
                    # 由于 point_set 结构， 满足 i<j<k
                    sum_weight = weight[i]+weight[j]+weight[k]
                    triangle_info = [i,j,k,sum_weight]
                    # i,j,k 三个点 记录和更新三角形信息
                    for lm in [i,j,k]:
                        if not max_triangle_point_dict[lm] or max_triangle_point_dict[lm][-1]<sum_weight:
                            max_triangle_point_dict[lm] = triangle_info
                        triangle_point_dict[lm].append([i,j,k])
                    # 三个条边 记录和更新三角形信息
                    for edge in [(i,j),(i,k),(j,k)]:
                        triangle_edge_dict[edge] = self.get_top3(triangle_edge_dict[edge],triangle_info)
 
        res = 0
        for i in range(0,n):
            # 点无三角形的情况
            if not max_triangle_point_dict[i]:
                continue
            max_triange = max_triangle_point_dict[i]
            # 两个三角形完全重合的情况，即一个三角形
            res = max(res,max_triange[-1])

            # 最大三角形 max_triange 和所有包含 i 的三角形一一组合
            for info in triangle_point_dict[i]:
                res = max(res,self.count_val(max_triange,info))
        
            # 两个包含max_triangle边（i,x),(i,y) 的 Top3 三角形一一组合
            max_points = max_triange[:3]
            max_points.remove(i)
            edge1,edge2 = [(i,x) if i<x else (x,i) for x in max_points]
            for info1 in triangle_edge_dict[edge1]:
                for info2 in triangle_edge_dict[edge2]:
                    res = max(res,self.count_val(info1,info2))
        
        return res
    
    def count_val(self, info1, info2):
        # 计算 两个三角的val总和， 过滤重复点
        all_points = set(info1[:3])|set(info2[:3])
        return sum([self.weight[x] for x in all_points])
        
    def get_top3(self, triangle_list, triangle_info):
        # 更新 同一条边 的 top3 的三角形
        if not triangle_list:
            return [triangle_info]
        if triangle_list[-1][-1]>=triangle_info[-1]:
            triangle_list.append(triangle_info)
            return triangle_list
        for index in range(0,len(triangle_list)):
            if triangle_list[index][-1]<triangle_info[-1]:
                triangle_list.insert(index,triangle_info)
                break
        triangle_list = triangle_list[:3]
        return triangle_list

复杂度分析

  • 时间复杂度：O(N\sqrt{N})，N 是顶点和边的数量级。

  • 空间复杂度：O(N)。

 Comments
On this page
LCP 16-游乐园的游览计划
  1. 题意概述：
    1. 考点一：找三角形
    2. 考点二：三角形拼接