LCP 16. 游乐园的游览计划 — Python3 实现题目理解小吴计划上午和下午各游玩一个以重点项目 A 为中心的三角形路径A-B-C-A两个三角形至少共享一个顶点求最大喜爱值之和。本质上是在图中找两个三角形它们至少共享一个顶点使得所有不同顶点的权值和最大。核心思路1. 找所有三元环三角形由于点数和边数同级N \approx M三元环最多 O(N\sqrt{N}) 个。使用度数定向优化枚举- 按度数排序边从度数大的点指向度数小的点- 枚举每个点 u标记其邻居再枚举邻居 v 的邻居 k若 k 也是 u 的邻居则找到三元环 u-v-k2. 三角形拼接鸽笼原理优化对于每个顶点 v收集所有包含 v 的三元环。按权值排序后最优解一定涉及权值前3大的三元环之一鸽笼原理因此只需枚举前3个与所有其他三元环组合。Python3 代码pythonfrom typing import Listclass Solution:def maxWeight(self, edges: List[List[int]], value: List[int]) - int:n len(value)# 1. 计算度数deg [0] * nfor u, v in edges:deg[u] 1deg[v] 1# 2. 度数定向从度数大的指向度数小的度数相同则编号大的指向编号小的# 这样每个点的出度为 O(sqrt(M))g [[] for _ in range(n)]for u, v in edges:if deg[u] deg[v] or (deg[u] deg[v] and u v):g[u].append(v)else:g[v].append(u)# 3. 找所有三元环# triple[v] 存储包含顶点 v 的所有三元环用另外两点表示方便后续计算triple [[] for _ in range(n)]vis [0] * nfor u in range(n):# 标记 u 的所有邻居for v in g[u]:vis[v] u 1 # 用 u1 避免每次清空数组for v in g[u]:for k in g[v]:if vis[k] u 1: # k 也是 u 的邻居找到三元环 u-v-kw value[u] value[v] value[k]# 存储三元环的另外两点和权值triple[u].append((w, v, k))triple[v].append((w, u, k))triple[k].append((w, u, v))# 4. 对每个顶点的三元环按权值降序排序for i in range(n):triple[i].sort(reverseTrue)# 5. 计算两个三元环合并后的权值去重def calc(t1, t2):# t1, t2 格式: (w, a, b) 表示三元环包含当前顶点和 a, bs set()# 当前顶点在调用时已知这里只存另外两点# 实际需要根据上下文调整这里简化处理points [t1[1], t1[2], t2[1], t2[2]]# 加上当前顶点在枚举时处理return sum(value[p] for p in set(points))ans 0# 6. 枚举每个顶点作为连接点for v in range(n):m len(triple[v])if m 0:continue# 只枚举前3大的三元环鸽笼原理保证最优解在其中for i in range(min(3, m)):w1, a1, b1 triple[v][i]# 情况1只用一个三元环上午下午同一个ans max(ans, w1)# 情况2与所有其他三元环组合for j in range(m):if i j:continuew2, a2, b2 triple[v][j]# 计算并集权值去重points {v, a1, b1, a2, b2}total sum(value[p] for p in points)ans max(ans, total)return ans更优的 Python 实现参考官方题解优化版pythonfrom typing import Listimport heapqclass Solution:def maxWeight(self, edges: List[List[int]], value: List[int]) - int:n len(value)# 度数定向deg [0] * nfor u, v in edges:deg[u] 1deg[v] 1g [[] for _ in range(n)]for u, v in edges:if (deg[u], u) (deg[v], v):u, v v, ug[u].append(v)# 找三元环triple [[] for _ in range(n)]vis [0] * nfor u in range(n):for v in g[u]:vis[v] 1for v in g[u]:for k in g[v]:if vis[k]:# 找到三元环 u-v-kw value[u] value[v] value[k]triple[u].append((w, min(v, k), max(v, k)))triple[v].append((w, min(u, k), max(u, k)))triple[k].append((w, min(u, v), max(u, v)))for v in g[u]:vis[v] 0ans 0# 对每个顶点取前5大的三元环进行组合保证覆盖最优解for v in range(n):if not triple[v]:continue# 按权值降序取前5个triple[v].sort(reverseTrue)top triple[v][:5]# 枚举所有配对for i in range(len(top)):w1, a1, b1 top[i]ans max(ans, w1) # 单个三元环for j in range(i 1, len(top)):w2, a2, b2 top[j]# 计算并集权值points {v}for p in [a1, b1, a2, b2]:points.add(p)total sum(value[p] for p in points)ans max(ans, total)return ans复杂度分析- 时间复杂度O(N\sqrt{N})三元环枚举使用度数定向优化每个顶点只需处理前几个最优三元环- 空间复杂度O(N\sqrt{N})存储所有三元环关键要点1. 度数定向将无向边定向为从高度数点指向低度数点保证每个点出度为 O(\sqrt{M})从而三元环枚举复杂度控制在 O(N\sqrt{N})2. 鸽笼原理对每个顶点只需考虑权值最大的前3-5个三元环即可覆盖最优解3. 去重计算两个三角形合并时共享顶点只计算一次权值