Kimi LeetCode 3547. 图中边值的最大和 Python3实现-北京尧图网络

以下是 LeetCode 3547. 图中边值的最大和的 Python3 实现。解题思路由于每个节点最多与其他两个节点相连整个图由若干链和环组成。1. 连通分量分类用 DFS/BFS 找出所有连通分量。若分量内所有节点度数均为 2则为环否则为链孤立点不贡献边权忽略。2. 处理顺序先处理环每个节点有两条边大数在环中能产生更多乘积再处理链按长度降序长链优先拿大数。3. 填数策略将剩余的最大数放在连通分量中间次大数交替向两边扩展使得大数尽量相邻双端队列模拟。时间复杂度 O(n \log n)空间复杂度 O(n)。---Python3 代码pythonfrom collections import dequefrom typing import Listclass 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] * ncycle_sizes [] # 环的大小path_sizes [] # 链的大小# 遍历每个连通分量for i in range(n):if seen[i]:continue# DFS 收集连通分量component []stack [i]seen[i] Truewhile stack:u stack.pop()component.append(u)for v in graph[u]:if not seen[v]:seen[v] Truestack.append(v)# 判断是否为环所有节点度数均为 2is_cycle Truefor u in component:if len(graph[u]) ! 2:is_cycle Falsebreakif 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(reverseTrue)for size in path_sizes:ans self._calc_score(n - size 1, n, False)n - sizereturn ansdef _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 0for val in range(right - 1, left - 1, -1):window_val dq.popleft()score window_val * valdq.append(val)# 如果是环首尾两个节点也相邻额外加上首尾乘积if is_cycle:score dq[0] * dq[-1]return score---关键说明要点说明连通分量分类所有节点度数均为 2 → 环否则为链含孤立点处理顺序环优先于链因为环的每个节点都有两条边大数在环中能产生更多乘积链按长度降序长链优先拿大数_calc_score 双端队列模拟最优排列。例如 [7..11] 填入 5 个节点的链排列为 8-10-11-9-7边权和 801109963 352环额外处理环首尾相连所以 dq[0] * dq[-1] 是最后一条边的贡献

Kimi LeetCode 3547. 图中边值的最大和 Python3实现

相关推荐

GHelper完整指南：5步轻松掌控华硕笔记本性能，告别臃肿官方软件

RAE递归对抗引擎优化：贝叶斯决策迭代收敛参数与混沌不确定性量化机制深度研究

【车间调度FJSP】基于全球邻域和爬山优化算法的模糊柔性车间调度问题研究（Matlab代码实现）

更多资讯

Wagtail 6.0.2 发布说明深度解析：Chooser 模态框、ModelViewSet 与 TableBlock 的 8 项关键修复

Waybar 日历周数显示错位、算错？这份快速修复指南一次讲清

pykan 实战：用 KAN 从二维哈密顿流场中无监督学习守恒律（Conservation Laws）

Megatron-LM 大型 PR 拆分实战：基于 CODEOWNERS 分组的最小审查集合拆分指南

amis 页面交互行为跟踪（tracker）实战指南：从采集到上报的完整方案

ClickHouse v21.7.3.14-stable 深度解析：从七个 Bug 修复看分布式查询与几何函数的内核细节

今日更新

51单片机开环控制磁阻传感器的硬件匹配与代码实现

AI Agent安全操作数据库：SQL注入防御与参数化查询实战

Android逆向实战：还原激励类App签到接口的签名算法

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？