这道题的核心是在无向图中找到两个共享顶点A的三角形（A-B-C-A 和 A-B'-C'-A），使得它们覆盖的不同顶点权值之和最大。
由于数据规模较大（顶点和边最多10000），暴力枚举所有三角形会超时，通常采用根号分治来优化。
Java实现代码
```java
import java.util.*;
class Solution {
public int maxWeight(int[][] edges, int[] value) {
int n = value.length;
// 1. 建图：邻接表（用于遍历） + 邻接矩阵（用于快速判断边是否存在）
List<Integer>[] graph = new List[n];
boolean[][] hasEdge = new boolean[n][n];
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
for (int[] e : edges) {
int u = e[0], v = e[1];
graph[u].add(v);
graph[v].add(u);
hasEdge[u][v] = hasEdge[v][u] = true;
}
// 2. 根号分治：度数 > limit 的为“大点”，否则为“小点”
int limit = (int) Math.sqrt(n);
boolean[] isBig = new boolean[n];
for (int i = 0; i < n; i++) {
if (graph[i].size() > limit) isBig[i] = true;
}
// 存储每个顶点参与的三角形（只存顶点三元组和权值和）
List<int[]>[] triByVertex = new List[n];
for (int i = 0; i < n; i++) triByVertex[i] = new ArrayList<>();
// 3. 枚举所有三角形
// 3.1 枚举小点 v：枚举其两个邻居 a, b，检查 a,b 是否相连
for (int v = 0; v < n; v++) {
if (isBig[v]) continue;
List<Integer> adj = graph[v];
for (int i = 0; i < adj.size(); i++) {
for (int j = i + 1; j < adj.size(); j++) {
int a = adj.get(i), b = adj.get(j);
if (hasEdge[a][b]) {
int sum = value[v] + value[a] + value[b];
triByVertex[v].add(new int[]{v, a, b, sum});
triByVertex[a].add(new int[]{v, a, b, sum});
triByVertex[b].add(new int[]{v, a, b, sum});
}
}
}
}
// 3.2 枚举大点：枚举任意三个大点，检查是否两两相连
List<Integer> bigNodes = new ArrayList<>();
for (int i = 0; i < n; i++) if (isBig[i]) bigNodes.add(i);
for (int i = 0; i < bigNodes.size(); i++) {
for (int j = i + 1; j < bigNodes.size(); j++) {
for (int k = j + 1; k < bigNodes.size(); k++) {
int a = bigNodes.get(i), b = bigNodes.get(j), c = bigNodes.get(k);
if (hasEdge[a][b] && hasEdge[a][c] && hasEdge[b][c]) {
int sum = value[a] + value[b] + value[c];
triByVertex[a].add(new int[]{a, b, c, sum});
triByVertex[b].add(new int[]{a, b, c, sum});
triByVertex[c].add(new int[]{a, b, c, sum});
}
}
}
}
// 4. 计算答案：枚举公共顶点 A，找两个最优三角形组合
int ans = 0;
for (int a = 0; a < n; a++) {
List<int[]> tris = triByVertex[a];
if (tris.size() < 2) {
// 只有一个三角形时，只能游玩一个，答案就是该三角形的权值和
if (tris.size() == 1) ans = Math.max(ans, tris.get(0)[3]);
continue;
}
// 按权值和降序排序，只需考虑前几个
tris.sort((x, y) -> y[3] - x[3]);
// 尝试前 min(5, size) 个组合，通常足够
for (int i = 0; i < Math.min(5, tris.size()); i++) {
for (int j = i + 1; j < Math.min(5, tris.size()); j++) {
int[] t1 = tris.get(i), t2 = tris.get(j);
Set<Integer> set = new HashSet<>();
set.add(t1[0]); set.add(t1[1]); set.add(t1[2]);
set.add(t2[0]); set.add(t2[1]); set.add(t2[2]);
int sum = 0;
for (int node : set) sum += value[node];
ans = Math.max(ans, sum);
}
}
}
return ans;
}
}
```
复杂度分析
· 时间复杂度：O(N√N)，在 N=10000 的规模下可接受。
· 空间复杂度：O(N + M)，用于存储图、邻接矩阵及三角形信息。
核心思路
1. 问题转化：将游玩路径抽象为两个共享顶点 A 的三角形。
2. 高效找三角形：利用“根号分治”平衡大小顶点的枚举开销，避免 O(N^3) 的暴力。
3. 枚举组合：对每个顶点 A，枚举其参与的所有三角形，取两个去重后权值和最大的组合。
4. 剪枝优化：只需考虑每个顶点下权值和最大的前几个三角形进行组合，无需全量枚举。
