制作网站设计的公司,辽宁短视频搜索seo哪家实惠,小程序微信如何开发,网站建设需求分析报告功能题目#xff1a;蓝桥杯2025年第十六届省赛真题-扫地机器人 - C语言网
用到算法#xff1a;基环树#xff0c;拓扑排序#xff0c;单调队列#xff0c;前缀和
参考讲解/思路详解#xff1a;蓝桥杯真题 - 扫地机器人_哔哩哔哩_bilibili
P12145 [蓝桥杯 2025 省 A] 扫地机…题目蓝桥杯2025年第十六届省赛真题-扫地机器人 - C语言网
用到算法基环树拓扑排序单调队列前缀和
参考讲解/思路详解蓝桥杯真题 - 扫地机器人_哔哩哔哩_bilibili
P12145 [蓝桥杯 2025 省 A] 扫地机器人 - 洛谷
code
#include bits/stdc.h
using namespace std;int main()
{// inputint n;cinn;vectorint w(n 1, 0), d(n 1, 0), vis(n 1, false);vectorvectorint g(n 1, vectorint());for(int i 0; i n; i){cinw[i];}for(int i 0; i n; i){int u, v; cinuv;u--; v--;// 保证下标一致g[u].push_back(v);g[v].push_back(u);d[u]; d[v];}// 拓扑排序标记非环上节点queueint 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环的长度vectorint 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);}vectorint 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]);}// 常规情况外部进环绕环半圈后出环dequepairint, 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]});}coutansendl;return 0;
}
