题目大意给定一个无向连通图每个点有一个点权现在要割下一些点使这些点形成森林且移除后剩下的图还是连通。问这些点最小的点权和。核心思路割完点后要使得剩下的图连通这让我们想起了割点我们知道一个无向连通图去掉一个割点后剩下的图是不连通的那么我们想诶这题的答案是不是最小非割点的点权呢答案是肯定的。假设最小非割点的点权为s ss。假如有多个点的点权加起来比s ss还要小如果这些点里面有割点那么移除后剩余的图肯定不连通如果这些点都不是割点说明这些点各自的点权都比s ss要小这与s ss是所有非割点的最小值矛盾。所以答案就是最小非割点的点权。我们可以通过 Tarjan 寻找割点不会的可以去模版学习一下把所有割点都标记最后循环一遍在非割点中取点权最小值即可。AC 代码#includebits/stdc.husingnamespacestd;usinglllonglong;constintINF0x3f3f3f3f;constll INFLL0x3f3f3f3f3f3f3f3fLL;constintN1e55;structedge{intto,next;}e[N2];intt,n,m,cnt,root,idx,head[N],dfn[N],low[N];ll ans,a[N];booliscut[N];// 标记割点的数组stackintstk;inlinevoidaddedge(intu,intv){e[cnt](edge){v,head[u]};head[u]cnt;}// 链式前向星voidtarjan(intu,intfa){// Tarjan 部分dfn[u]low[u]idx;stk.push(u);intnt0;for(intihead[u];~i;ie[i].next){intve[i].to;if(vfa)continue;if(!dfn[v]){nt;tarjan(v,u);low[u]min(low[u],low[v]);if((urootnt1)||(u!rootlow[v]dfn[u])){if(!iscut[u])iscut[u]true;}}else{low[u]min(low[u],dfn[v]);}}}intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cint;while(t--){cntidx0;ansINFLL;// 把 ans 初始化为最大值cinnm;for(inti1;in;i){cina[i];dfn[i]low[i]0;head[i]-1;iscut[i]false;}while(!stk.empty())stk.pop();for(inti1,u,v;im;i){cinuv;addedge(u,v);addedge(v,u);}for(inti1;in;i){if(!dfn[i])rooti,tarjan(i,-1);// 如果当前点没有被访问过就以当前点为根节点跑一遍 Tarjan}for(inti1;in;i){if(!iscut[i])ansmin(ans,a[i]);// 更新非割点点权最小值}coutans\n;// 输出结果}return0;}完结撒花 ✿✿ヽ(°▽°)ノ✿