Kimi LeetCode 3547. 图中边值的最大和 Python3实现
以下是 LeetCode 3547. 图中边值的最大和 的 Python3 实现。
解题思路
由于每个节点最多与其他两个节点相连，整个图由若干链和环组成。
1. 连通分量分类：用 DFS/BFS 找出所有连通分量。若分量内所有节点度数均为 2，则为环；否则为链（孤立点不贡献边权，忽略）。
2. 处理顺序：先处理环（每个节点有两条边，大数在环中能产生更多乘积），再处理链（按长度降序，长链优先拿大数）。
3. 填数策略：将剩余的最大数放在连通分量中间，次大数交替向两边扩展，使得大数尽量相邻（双端队列模拟）。
时间复杂度 O(n \log n)，空间复杂度 O(n)。
---
Python3 代码
```python
from collections import deque
from typing import List
class Solution:
def maxScore(self, n: int, edges: List[List[int]]) -> int:
# 建图
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
seen = [False] * n
cycle_sizes = [] # 环的大小
path_sizes = [] # 链的大小
# 遍历每个连通分量
for i in range(n):
if seen[i]:
continue
# DFS 收集连通分量
component = []
stack = [i]
seen[i] = True
while stack:
u = stack.pop()
component.append(u)
for v in graph[u]:
if not seen[v]:
seen[v] = True
stack.append(v)
# 判断是否为环：所有节点度数均为 2
is_cycle = True
for u in component:
if len(graph[u]) != 2:
is_cycle = False
break
if is_cycle:
cycle_sizes.append(len(component))
elif len(component) > 1:
path_sizes.append(len(component))
# 孤立点（size == 1）不贡献边权，无需处理
ans = 0
# 先处理环：从剩余的最大数中分配
for size in cycle_sizes:
ans += self._calc_score(n - size + 1, n, True)
n -= size
# 链按长度从大到小排序，优先处理长链
path_sizes.sort(reverse=True)
for size in path_sizes:
ans += self._calc_score(n - size + 1, n, False)
n -= size
return ans
def _calc_score(self, left: int, right: int, is_cycle: bool) -> int:
"""
将 [left, right] 范围内的数填入一个连通分量，计算最大边权和。
策略：双端队列模拟"中间放大数，向两边递减"的排列。
初始放入两个 right，从 right-1 递减到 left，每次取出队首与当前值相乘，
再将当前值放入队尾。
"""
dq = deque()
dq.append(right)
dq.append(right)
score = 0
for val in range(right - 1, left - 1, -1):
window_val = dq.popleft()
score += window_val * val
dq.append(val)
# 如果是环，首尾两个节点也相邻，额外加上首尾乘积
if is_cycle:
score += dq[0] * dq[-1]
return score
```
---
关键说明
要点 说明
连通分量分类 所有节点度数均为 2 → 环；否则为链（含孤立点）
处理顺序 环优先于链，因为环的每个节点都有两条边，大数在环中能产生更多乘积；链按长度降序，长链优先拿大数
`_calc_score` 双端队列模拟最优排列。例如 `[7..11]` 填入 5 个节点的链，排列为 `8-10-11-9-7`，边权和 `80+110+99+63 = 352`
环额外处理 环首尾相连，所以 `dq[0] * dq[-1]` 是最后一条边的贡献