扫地机器人（2025蓝桥杯省A组 H题）

题目：蓝桥杯2025年第十六届省赛真题-扫地机器人 - C语言网

用到算法：基环树，拓扑排序，单调队列，前缀和

参考讲解/思路详解：蓝桥杯真题 - 扫地机器人_哔哩哔哩_bilibili

P12145 [蓝桥杯 2025 省 A] 扫地机器人 - 洛谷

code

#include <bits/stdc++.h>
using namespace std;int main()
{// inputint n;cin>>n;vector<int> w(n + 1, 0), d(n + 1, 0), vis(n + 1, false);vector<vector<int>> g(n + 1, vector<int>());for(int i = 0; i < n; i++){cin>>w[i];}for(int i = 0; i < n; i++){int u, v; cin>>u>>v;u--; v--;// 保证下标一致g[u].push_back(v);g[v].push_back(u);d[u]++; d[v]++;}// 拓扑排序，标记非环上节点queue<int> q;for(int i = 0; i < n; i++){if(d[i] == 1){vis[i] = true;q.push(i);}}while(q.size()){int pnt = q.front();q.pop();for(auto son:g[pnt]){if(--d[son] == 1) {q.push(son);vis[son] = true;}}}// 拆环， 环上每点当root跑环的直径int st = 0, cnt = 0;// st：环上任意一点，cnt：环的长度vector<int> f1(2 * n + 2, 0), f2(2 * n + 2, 0);int ans = 0;auto dfs = [&](auto dfs, int u, int fa)->void{f1[u] = w[u];f2[u] = w[u];for(int l : g[u]){if(l == fa || !vis[l]) continue;dfs(dfs, l, u);if(f1[l] + w[u] > f1[u]){f2[u] = f1[u];f1[u] = f1[l] + w[u];}else f2[u] = max(f2[u], f1[l] + w[u]);}ans = max(ans, f1[u] + f2[u] - w[u]);// 第一种情况，最长路径不过环};for(int i = 0; i < n; i++){if(vis[i]) continue;cnt++;st = i;dfs(dfs, i, -1);}vector<int> dist(2 * cnt + 2, 0), dp1(2 * cnt + 2, 0), dp2(2 * cnt + 2, 0);int idx = 0;auto dfs1 = [&](auto dfs1, int u, int fa)->void{dp1[++idx] = f1[u] - w[u];dp2[idx] = f2[u] - w[u];dist[idx] = w[u];vis[u] = true;// 防止无线循环for(int l : g[u]){if(l == fa || vis[l]) continue;dfs1(dfs1, l, u);}};dfs1(dfs1, st, -1);// 破链成环for(int i = 1; i <= cnt; i++){dp1[i + cnt] = dp1[i];dp2[i + cnt] = dp2[i];dist[i + cnt] = dist[i];}for(int i = 1; i <= 2 * cnt; i++){dist[i] = dist[i] + dist[i -1];}// 特判环上点权之和加上某一棵子树根的最长链加次长链。for(int i = 1; i <= cnt; i++){ans = max(ans, dist[cnt] + dp1[i] + dp2[i]);}// 常规情况，外部进环，绕环半圈后出环deque<pair<int, int>> dq;// 单调队列，维护dp1[i] - dist[i-1]的最值for(int j = 1; j <= 2 * cnt; j++)// 以j结尾的最长路径{while(dq.size() && j - dq.front().first + 1 > cnt) dq.pop_front();if(dq.size()) ans = max(ans, dist[j] + dp1[j] + dq.front().second);// 细节，在将j入dp前更新answhile(dq.size() && dq.back().second < dp1[j] - dist[j - 1]) dq.pop_back();dq.push_back({j, dp1[j] - dist[j - 1]});}cout<<ans<<endl;return 0;
}