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

· · 题解

前言

第一次场切绿题！

前置知识

割点。

题目解析

题出的很有意思。

注意到权值是非负的并且取下的图权值和最小，那不妨取下一个点，显然多取一个点一定会增加总权值。“森林”难倒了不少选手吧。

于是我们找到所有割点，不是割点的就可以取下，取权值最小的即可。

这题卡常，需要用快读快写优化。

正解代码

代码没什么重点，会割点的应该可以不看题目做，实在是过于板子了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int sz=1e5;
int root=1,cnt=0;
vector<vector<int>> idc(sz,vector<int>(0));
int num[sz]={0};
int low[sz]={0};
int a[sz]={0};
bool flag[sz]={0};
//#define getchar_unlocked getchar
//#define putchar_unlocked putchar
inline void read(int& x)
{
    x=0;
    char ch=getchar_unlocked();
    bool flag=false;
    while(ch<'0' || ch>'9')
    {
        if(ch=='-') flag=1;
        ch=getchar_unlocked();
    }
    while(ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar_unlocked();
    }
    if(flag) x=-x;
}
inline void write(int x)
{
    if(x<0)
    {
        putchar_unlocked('-');
        x=-x;
    }
    if(x>9) write(x/10);
    putchar_unlocked(x%10+'0');
}

void dfs(int c,int fa)
{
    cnt++;
    int child=0;
    num[c]=low[c]=cnt;
    for(int i:idc[c])
    {
        if(num[i]==0)
        {
            child++;
            dfs(i,c);
            low[c]=min(low[c],low[i]);
            if(c!=root && low[i]>=num[c])
            {
                flag[c]=1;
            }
            if(c==root && child>=2)
            {
                flag[c]=1;
            }
        }
        else if(i!=fa)
        {
            low[c]=min(low[c],num[i]);
        }
    }
}
signed main()
{

    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
    read(n);read(m);
    for(int i=1;i<=n;i++)
    {
        read(a[i]);
        idc[i].clear();
        num[i]=low[i]=flag[i]=0;
    }
    for(int i=1;i<=m;i++)
    {
        int x,y;
        read(x);read(y);
        idc[y].push_back(x);
        idc[x].push_back(y);
    }
    for(int i=1;i<=n;i++)
    {
        if(num[i]==0)
        {
            root=i;
            dfs(i,-1);
        }
    }
    int ans=INT_MAX;
    for(int i=1;i<=n;i++)
    {
        if(!flag[i])
        {
            ans=min(ans,a[i]);
        }
    }
    write(ans);
        putchar('\n');
    }
    return 0;
}