Kimi LeetCode 3547. 图中边值的最大和 Rust实现
以下是 LeetCode 3547. 图中边值的最大和 的 Rust 实现。
解题思路
由于每个节点最多与其他两个节点相连，整个图由若干链和环组成。
1. 连通分量分类：用 DFS 找出所有连通分量。若分量内所有节点度数均为 2，则为环；否则为链（孤立点不贡献边权，忽略）。
2. 处理顺序：先处理环（每个节点有两条边，大数在环中能产生更多乘积），再处理链（按长度降序，长链优先拿大数）。
3. 填数策略：将剩余的最大数放在连通分量中间，次大数交替向两边扩展，使得大数尽量相邻（双端队列模拟）。
时间复杂度 O(n \log n)，空间复杂度 O(n)。
---
Rust 代码
```rust
use std::collections::VecDeque;
struct Solution;
impl Solution {
pub fn max_score(n: i32, edges: Vec<Vec<i32>>) -> i64 {
let n = n as usize;
let mut graph = vec![vec![]; n];
for edge in &edges {
let u = edge[0] as usize;
let v = edge[1] as usize;
graph[u].push(v);
graph[v].push(u);
}
let mut seen = vec![false; n];
let mut cycle_sizes = vec![];
let mut path_sizes = vec![];
// 遍历每个连通分量
for i in 0..n {
if seen[i] {
continue;
}
// DFS 收集连通分量
let mut component = vec![];
let mut stack = vec![i];
seen[i] = true;
while let Some(u) = stack.pop() {
component.push(u);
for &v in &graph[u] {
if !seen[v] {
seen[v] = true;
stack.push(v);
}
}
}
// 判断是否为环：所有节点度数均为 2
let is_cycle = component.iter().all(|&u| graph[u].len() == 2);
if is_cycle {
cycle_sizes.push(component.len());
} else if component.len() > 1 {
path_sizes.push(component.len());
}
// 孤立点（size == 1）不贡献边权，无需处理
}
let mut ans: i64 = 0;
let mut remaining = n as i64;
// 先处理环：从剩余的最大数中分配
for size in cycle_sizes {
let size = size as i64;
ans += Self::calc_score(remaining - size + 1, remaining, true);
remaining -= size;
}
// 链按长度从大到小排序，优先处理长链
path_sizes.sort_by(|a, b| b.cmp(a));
for size in path_sizes {
let size = size as i64;
ans += Self::calc_score(remaining - size + 1, remaining, false);
remaining -= size;
}
ans
}
/// 将 [left, right] 范围内的数填入一个连通分量，计算最大边权和。
///
/// 策略：双端队列模拟"中间放大数，向两边递减"的排列。
/// 初始放入两个 right，从 right-1 递减到 left，每次取出队首与当前值相乘，
/// 再将当前值放入队尾。
fn calc_score(left: i64, right: i64, is_cycle: bool) -> i64 {
let mut dq = VecDeque::new();
dq.push_back(right);
dq.push_back(right);
let mut score: i64 = 0;
for val in (left..right).rev() {
let window_val = dq.pop_front().unwrap();
score += window_val * val;
dq.push_back(val);
}
// 如果是环，首尾两个节点也相邻，额外加上首尾乘积
if is_cycle {
score += dq.front().unwrap() * dq.back().unwrap();
}
score
}
}
```
---
关键说明
要点 说明
连通分量分类 所有节点度数均为 2 → 环；否则为链（含孤立点）
处理顺序 环优先于链，因为环的每个节点都有两条边，大数在环中能产生更多乘积；链按长度降序，长链优先拿大数
`calc_score` 双端队列模拟最优排列。例如 `[7..11]` 填入 5 个节点的链，排列为 `8-10-11-9-7`，边权和最大
环额外处理 环首尾相连，所以 `dq.front() * dq.back()` 是最后一条边的贡献