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

以下是 LeetCode 3547. 图中边值的最大和 的 C++ 实现。

解题思路

由于每个节点最多与其他两个节点相连，整个图由若干链和环组成。

1. 连通分量分类：用 DFS 找出所有连通分量。若分量内所有节点度数均为 2，则为环；否则为链（孤立点不贡献边权，忽略）。
2. 处理顺序：先处理环（每个节点有两条边，大数在环中能产生更多乘积），再处理链（按长度降序，长链优先拿大数）。
3. 填数策略：将剩余的最大数放在连通分量中间，次大数交替向两边扩展，使得大数尽量相邻（双端队列模拟）。

时间复杂度 O(n \log n)，空间复杂度 O(n)。

---

C++ 代码

```cpp
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

class Solution {
public:
long long maxScore(int n, vector<vector<int>>& edges) {
vector<vector<int>> graph(n);
for (auto& edge : edges) {
int u = edge[0], v = edge[1];
graph[u].push_back(v);
graph[v].push_back(u);
}

vector<bool> seen(n, false);
vector<int> cycleSizes; // 环的大小
vector<int> pathSizes; // 链的大小

// 遍历每个连通分量
for (int i = 0; i < n; ++i) {
if (seen[i]) continue;

// DFS 收集连通分量
vector<int> component;
vector<int> stack = {i};
seen[i] = true;

while (!stack.empty()) {
int u = stack.back();
stack.pop_back();
component.push_back(u);
for (int v : graph[u]) {
if (!seen[v]) {
seen[v] = true;
stack.push_back(v);
}
}
}

// 判断是否为环：所有节点度数均为 2
bool isCycle = true;
for (int u : component) {
if (graph[u].size() != 2) {
isCycle = false;
break;
}
}

if (isCycle) {
cycleSizes.push_back(component.size());
} else if (component.size() > 1) {
pathSizes.push_back(component.size());
}
// 孤立点（size == 1）不贡献边权，无需处理
}

long long ans = 0;
long long remaining = n;

// 先处理环：从剩余的最大数中分配
for (int size : cycleSizes) {
ans += calcScore(remaining - size + 1, remaining, true);
remaining -= size;
}

// 链按长度从大到小排序，优先处理长链
sort(pathSizes.rbegin(), pathSizes.rend());
for (int size : pathSizes) {
ans += calcScore(remaining - size + 1, remaining, false);
remaining -= size;
}

return ans;
}

private:
/**
* 将 [left, right] 范围内的数填入一个连通分量，计算最大边权和。
*
* 策略：双端队列模拟"中间放大数，向两边递减"的排列。
* 初始放入两个 right，从 right-1 递减到 left，每次取出队首与当前值相乘，
* 再将当前值放入队尾。
*/
long long calcScore(long long left, long long right, bool isCycle) {
deque<long long> dq;
dq.push_back(right);
dq.push_back(right);
long long score = 0;

for (long long val = right - 1; val >= left; --val) {
long long windowVal = dq.front();
dq.pop_front();
score += windowVal * val;
dq.push_back(val);
}

// 如果是环，首尾两个节点也相邻，额外加上首尾乘积
if (isCycle) {
score += dq.front() * dq.back();
}

return score;
}
};
```

---

关键说明

要点 说明
连通分量分类 所有节点度数均为 2 → 环；否则为链（含孤立点）
处理顺序 环优先于链，因为环的每个节点都有两条边，大数在环中能产生更多乘积；链按长度降序，长链优先拿大数
`calcScore` 双端队列模拟最优排列。例如 `[7..11]` 填入 5 个节点的链，排列为 `8-10-11-9-7`，边权和最大
环额外处理 环首尾相连，所以 `dq.front() * dq.back()` 是最后一条边的贡献