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

· · 题解

题意：

给定一个 n 点 m 边的简单无向连通图，每个点有非负点权。要求选择一个非空点集 S，使得：

  1. 导出的子图 G_S 是森林（无环）。
  2. 删去 S 中的点后，剩余图仍连通。

思路

显然，最优解一定是之包含一个点。

假设最优解选取了点集 S，且 S 中至少包含两个点（即 |S| \ge 2|S| \ge 2）。我们在 S 中任选一点 v，考虑只选取 v 这一个点作为新方案，单个点没有边，显然满足森林的定义。且代价更优，因为题目保证所有点权都是非负数。

所以只要这个点不是割点显然比多个点情况下优秀，因为割点下剩余图不联通。

那就好做了，把割点求出来，遍历一下非割点中的找最小值即可，Tarjan 求割点的时间复杂度为 O(n+m) 的，总时间复杂度就是 O(\sum n + \sum m) 的，轻松通过。

code

#include<bits/stdc++.h>
#define int long long
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#define putchar_unlocked _putchar_nolock
#endif
#define endl '\n'
static char printff[20];
using namespace std;
const int N = 100005;
vector<int> edge[N];
int dfn[N],low[N],timer;
bool flagg[N];
int a[N];
int n,m;
int read(){
    int k = 0,f = 1,c = getchar_unlocked();
    for(;!isdigit(c);c = getchar_unlocked()){
        if(c == '-')
            f = -1;
    }
    for(;isdigit(c);c = getchar_unlocked())
        k = k * 10 +(c ^ 48);
    return k * f;
}
void print(int p){
    unsigned int x = p;
    if(p < 0){
        putchar_unlocked('-');
        x = -x;
    }
    if(x == 0){
        putchar_unlocked('0');
        return;
    }
    int len = 0;
    while(x > 0){
        printff[len++] = x % 10 + '0';
        x /= 10;
    }
    while(len > 0){
        putchar_unlocked(printff[--len]);
    }
}
void fast(bool p){
    if(p){
        ios::sync_with_stdio(0);
        cin.tie(nullptr);
        return;
    }else{
        return;
    }
}
void tarjan(int u,int fa){
    dfn[u] = low[u] = ++timer;
    int child = 0;
    for(int v : edge[u]){
        if(!dfn[v]){
            child++;
            tarjan(v,u);
            low[u] = min(low[u],low[v]);
            if(fa != 0 && low[v] >= dfn[u]){
                flagg[u] = true;
            }
        } else if(v != fa){
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(fa == 0 && child >= 2){
        flagg[u] = true;
    }
}
signed main(){
    fast(0);
    int T = read();
    while(T--){
        n = read();m = read();
        timer = 0;
        for(int i = 1;i <= n;i++){
            edge[i].clear();
            dfn[i] = low[i] = 0;
            flagg[i] = false;
            a[i] = read();
        }
        for(int i = 0;i < m;i++){
            int u = read(),v = read();
            edge[u].push_back(v);
            edge[v].push_back(u);
        }
        if(n == 1){
            print(a[1]);
            putchar_unlocked('\n');
            continue;
        }
        tarjan(1, 0);
        int ans = LLONG_MAX;
        for (int i = 1;i <= n;i++){
            if (!flagg[i]){
                ans = min(ans, a[i]);
            }
        }
        print(ans);
        putchar_unlocked('\n');
    }
    return 0;
}