题解：P16825 [AFOI 2025] B.岁月

· · 题解

有点太笨蛋了这题。

点权非负，容易发现取出来一个点是满足条件且最优的，任何一个取出来多于一个点的方案扔回去一个点都是不会破坏合法性且不劣的，故得证。

因此我们考虑哪些点可以拿，这个点拿出来以后不能破坏原图连通性，故这个点不能是割点。

跑个 tarjan 把割点标记出来就没了。

代码是贺的割点模版。

#include<bits/stdc++.h>
using namespace std;
int n,m,root,dfn[100005],low[100005];
vector<int>ve[100005];
int ans,flc;
bool gd[100005];
void dfs(int x,int fa){
    dfn[x]=low[x]=++flc;
    int son=0;
    for(int i=0;i<ve[x].size();i++)
    if(!dfn[ve[x][i]]){
        son++;
        dfs(ve[x][i],x);
        low[x]=min(low[x],low[ve[x][i]]);
        if(low[ve[x][i]]>=dfn[x]&&x!=root)ans+=!gd[x],gd[x]=1;
    }else if(fa!=ve[x][i])low[x]=min(low[x],dfn[ve[x][i]]);
    if(son>1&&x==root)ans+=!gd[x],gd[x]=1;
}
int qwq[100005];
void solve(){
    cin>>n>>m;
    ans=flc=0;
    for(int i=1;i<=n;i++)
    cin>>qwq[i],ve[i].clear(),gd[i]=dfn[i]=low[i]=0;
    while(m--){
        int u,v;
        cin>>u>>v;
        ve[u].push_back(v);
        ve[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
    if(!dfn[i])root=i,dfs(i,0);
    int mn=1e9;
    for(int i=1;i<=n;i++)
    if(!gd[i])mn=min(mn,qwq[i]);
    cout<<mn<<'\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}
//「不不不。这几位无论怎么看都是大家闺秀。坦白讲是不太好听，但我们师团可是下流分子的巢窟耶！收容她们真的行吗？」

//「我说你啊，怎么朝着最高负责人把这里讲成下流分子的巢窟。」

//「您能否认吗？」