以下是 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 代码rustuse std::collections::HashSet;impl Solution {pub fn max_weight(edges: VecVeci32, value: Veci32) - i32 {let n value.len();let m edges.len();// 建图 边哈希表 O(1) 查询let mut adj: VecVecusize 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: VecVecTriangle vec![Vec::new(); n];// 每个顶点的 Top 3 三角形let mut top3_vertex: Vec[OptionTriangle; 3] vec![[None; 3]; n];// 每条边的 Top 3 三角形let mut top3_edge: std::collections::HashMap(usize, usize), [OptionTriangle; 3] std::collections::HashMap::new();// 将三角形按权值和降序插入 Top 3fn insert_top3(arr: mut [OptionTriangle; 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: Vecusize Vec::new();for u in 0..n {if adj[u].len() threshold { big_vertices.push(u); }}let big_set: HashSetusize 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: Veci32) - 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 的 Toplet 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) Kimi LeetCode LCP 16. 游乐园的游览计划 Rust实现
以下是 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 代码rustuse std::collections::HashSet;impl Solution {pub fn max_weight(edges: VecVeci32, value: Veci32) - i32 {let n value.len();let m edges.len();// 建图 边哈希表 O(1) 查询let mut adj: VecVecusize 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: VecVecTriangle vec![Vec::new(); n];// 每个顶点的 Top 3 三角形let mut top3_vertex: Vec[OptionTriangle; 3] vec![[None; 3]; n];// 每条边的 Top 3 三角形let mut top3_edge: std::collections::HashMap(usize, usize), [OptionTriangle; 3] std::collections::HashMap::new();// 将三角形按权值和降序插入 Top 3fn insert_top3(arr: mut [OptionTriangle; 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: Vecusize Vec::new();for u in 0..n {if adj[u].len() threshold { big_vertices.push(u); }}let big_set: HashSetusize 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: Veci32) - 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 的 Toplet 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)