以下是 LeetCode LCP 16. 游乐园的游览计划 的 Rust 实现。
题目理解
小吴计划上午和下午各走一个三角形路径（`A-B-C-A` 和 `A-B'-C'-A`），两个路径至少共享一个顶点 `A`。重复游玩同一个项目不重复计分。目标是最大化所有不同顶点的喜爱值之和。
等价于：在图中找两个三角形，它们至少共享一个顶点，使得所有不同顶点的权值和最大。
核心算法
采用 根号分解 (Sqrt Decomposition) 找所有三角形，时间复杂度 O(N\sqrt{N})：
1. 找三角形：设阈值 T = \sqrt{M}
- 小度点（度数 \le T）：枚举其邻居中所有点对，用哈希表 O(1) 判断是否有边
- 大度点（度数 > T）：大度点最多 \sqrt{N} 个，直接枚举所有三元组
2. 三角形拼接：枚举重合点 x，设包含 x 的最大三角形为 \triangle xab
- 与所有含 x 的三角形组合
- 边 xa 的 Top 三角形 + 边 xb 的 Top 三角形组合（各取 Top 3 避免点重复）
3. 重合边的情况：同一条边的 Top 2 三角形直接组合
Rust 代码
```rust
use std::collections::HashSet;
impl Solution {
pub fn max_weight(edges: Vec<Vec<i32>>, value: Vec<i32>) -> i32 {
let n = value.len();
let m = edges.len();
// 建图 + 边哈希表 O(1) 查询
let mut adj: Vec<Vec<usize>> = vec![Vec::new(); n];
let mut edge_set: HashSet<(usize, usize)> = HashSet::new();
for e in &edges {
let u = e[0] as usize;
let v = e[1] as usize;
adj[u].push(v);
adj[v].push(u);
edge_set.insert((u.min(v), u.max(v)));
}
// 三角形结构：顶点已排序 a < b < c
#[derive(Clone, Copy, Debug)]
struct Triangle {
a: usize,
b: usize,
c: usize,
sum: i32,
}
// 每个顶点关联的所有三角形
let mut vertex_triangles: Vec<Vec<Triangle>> = vec![Vec::new(); n];
// 每个顶点的 Top 3 三角形
let mut top3_vertex: Vec<[Option<Triangle>; 3]> = vec![[None; 3]; n];
// 每条边的 Top 3 三角形
let mut top3_edge: std::collections::HashMap<(usize, usize), [Option<Triangle>; 3]> =
std::collections::HashMap::new();
// 将三角形按权值和降序插入 Top 3
fn insert_top3(arr: &mut [Option<Triangle>; 3], tri: Triangle) {
for i in 0..3 {
if let Some(t) = arr[i] {
if t.a == tri.a && t.b == tri.b && t.c == tri.c { return; }
}
}
let mut pos = 3;
for i in 0..3 {
if arr[i].is_none() || arr[i].unwrap().sum < tri.sum {
pos = i; break;
}
}
if pos < 3 {
for i in (pos + 1..3).rev() { arr[i] = arr[i - 1]; }
arr[pos] = Some(tri);
}
}
let threshold = (m as f64).sqrt() as usize + 1;
// 收集大度点
let mut big_vertices: Vec<usize> = Vec::new();
for u in 0..n {
if adj[u].len() > threshold { big_vertices.push(u); }
}
let big_set: HashSet<usize> = big_vertices.iter().copied().collect();
// 邻居排序：大度点在前，便于后续处理
for u in 0..n {
adj[u].sort_by_key(|&v| if big_set.contains(&v) { 0 } else { 1 });
}
// ===== 根号分解找所有三角形 =====
// 小度点：枚举邻居点对
for u in 0..n {
if adj[u].len() <= threshold {
let neighbors = &adj[u];
for i in 0..neighbors.len() {
for j in (i + 1)..neighbors.len() {
let v = neighbors[i];
let w = neighbors[j];
if edge_set.contains(&(v.min(w), v.max(w))) {
let a = u.min(v).min(w);
let c = u.max(v).max(w);
let b = u + v + w - a - c;
let sum = value[a] + value[b] + value[c];
let tri = Triangle { a, b, c, sum };
vertex_triangles[a].push(tri);
vertex_triangles[b].push(tri);
vertex_triangles[c].push(tri);
insert_top3(&mut top3_vertex[a], tri);
insert_top3(&mut top3_vertex[b], tri);
insert_top3(&mut top3_vertex[c], tri);
let e1 = (a, b); let e2 = (a, c); let e3 = (b, c);
top3_edge.entry(e1).or_insert([None; 3]);
insert_top3(top3_edge.get_mut(&e1).unwrap(), tri);
top3_edge.entry(e2).or_insert([None; 3]);
insert_top3(top3_edge.get_mut(&e2).unwrap(), tri);
top3_edge.entry(e3).or_insert([None; 3]);
insert_top3(top3_edge.get_mut(&e3).unwrap(), tri);
}
}
}
}
}
// 大度点：枚举三元组（大度点最多 √N 个）
for i in 0..big_vertices.len() {
for j in (i + 1)..big_vertices.len() {
for k in (j + 1)..big_vertices.len() {
let a = big_vertices[i];
let b = big_vertices[j];
let c = big_vertices[k];
if edge_set.contains(&(a.min(b), a.max(b))) &&
edge_set.contains(&(a.min(c), a.max(c))) &&
edge_set.contains(&(b.min(c), b.max(c))) {
let sa = a.min(b).min(c);
let sc = a.max(b).max(c);
let sb = a + b + c - sa - sc;
let sum = value[sa] + value[sb] + value[sc];
let tri = Triangle { a: sa, b: sb, c: sc, sum };
vertex_triangles[sa].push(tri);
vertex_triangles[sb].push(tri);
vertex_triangles[sc].push(tri);
insert_top3(&mut top3_vertex[sa], tri);
insert_top3(&mut top3_vertex[sb], tri);
insert_top3(&mut top3_vertex[sc], tri);
let e1 = (sa, sb); let e2 = (sa, sc); let e3 = (sb, sc);
top3_edge.entry(e1).or_insert([None; 3]);
insert_top3(top3_edge.get_mut(&e1).unwrap(), tri);
top3_edge.entry(e2).or_insert([None; 3]);
insert_top3(top3_edge.get_mut(&e2).unwrap(), tri);
top3_edge.entry(e3).or_insert([None; 3]);
insert_top3(top3_edge.get_mut(&e3).unwrap(), tri);
}
}
}
}
// 合并两个三角形，去重计权值
fn combine(t1: Triangle, t2: Triangle, value: &Vec<i32>) -> i32 {
let mut sum = t1.sum;
if t2.a != t1.a && t2.a != t1.b && t2.a != t1.c { sum += value[t2.a]; }
if t2.b != t1.a && t2.b != t1.b && t2.b != t1.c { sum += value[t2.b]; }
if t2.c != t1.a && t2.c != t1.b && t2.c != t1.c { sum += value[t2.c]; }
sum
}
let mut ans = 0i32;
// Case 1: 两三角形共享一条边
for (_, arr) in &top3_edge {
if let Some(t1) = arr[0] {
ans = ans.max(t1.sum);
if let Some(t2) = arr[1] {
ans = ans.max(combine(t1, t2, &value));
}
}
}
// Case 2: 两三角形仅共享一个顶点
for x in 0..n {
if top3_vertex[x][0].is_none() { continue; }
let max_tri = top3_vertex[x][0].unwrap();
// 2a: 最大三角形与所有含 x 的三角形组合
for &tri in &vertex_triangles[x] {
ans = ans.max(combine(max_tri, tri, &value));
}
// 2b: 边 xa 的 Top + 边 xb 的 Top
let mut others = Vec::new();
for &v in &[max_tri.a, max_tri.b, max_tri.c] {
if v != x { others.push(v); }
}
let edge1 = (x.min(others[0]), x.max(others[0]));
let edge2 = (x.min(others[1]), x.max(others[1]));
let arr1 = top3_edge.get(&edge1).copied().unwrap_or([None; 3]);
let arr2 = top3_edge.get(&edge2).copied().unwrap_or([None; 3]);
for i in 0..3 {
if let Some(t1) = arr1[i] {
for j in 0..3 {
if let Some(t2) = arr2[j] {
ans = ans.max(combine(t1, t2, &value));
}
}
}
}
}
ans
}
}
```
复杂度分析
- 时间复杂度：O(N\sqrt{N})，其中 N 为顶点和边的数量级
- 小度点枚举：\sum \deg(v)^2 \le \sqrt{N} \cdot M = N\sqrt{N}
- 大度点枚举：(\sqrt{N})^3 = N\sqrt{N}
- 拼接阶段：每个顶点的三角形数可控
- 空间复杂度：O(N\sqrt{N})，存储所有三角形及相关信息
[下载 Rust 源码](sandbox:///mnt/agents/output/lcp16_rust.rs)
