题解：P9424 [蓝桥杯 2023 国 B] 删边问题

uiii_ · 2025-11-25 11:28:42 · 题解

题意

给定一个无向图 M，删除一条边后满足剩余图恰好有 2 个强连通分量。

输出合法方案中两强连通分量点权差最小值，无合法方案则输出 -1。

思路

看到联通分量和删边，自然而然地想到桥（割边）。

我们对原图中连通分量个数 scc 进行讨论。

scc>2
易得此时无论删除哪一条边 scc 都不可能等于 2，直接输出 -1 即可。
scc=2
此时已经有两个连通分量，若要使连通分量个数不变，我们需要删除一条非桥边。

简单证明一下：如果我们删除的边为桥，那么其所在联通分量便会分裂为多个联通分量。此时 scc>2，不符合题意。

若存在非桥边，输出答案即为两个初始连通分量点权和之差的绝对值。

不存在则输出 -1。
scc=1
需要删除桥。

那么该如何计算删除后两连通分量之差的最小值呢？

可以将图搞成 dfs 生成树，在 Tarjan 求桥的过程中我们可以计算出每个节点的子树点权之和。

设总点权为 sum，存在边 (u,v) 为桥，a_v 表示 v 的子树和。易得另一部分点权和即为 sum-a_v，两部分之差 ans=\left\vert sum-2a_v\right\vert。

由此，在这一情况中，若有桥则输出 ans；无桥则输出 -1。

一些细节

十年 OI 一场空，不开 long long 见祖宗。

Code

#include<bits/stdc++.h>
#define int long long
#define JiuKu champion 
using namespace std;
const int N=200005;
int n,m,w[N],head[N],tmp[N],f[N],flag,cnt,sum,ans=1e18,scc[N],dfn[N],low[N];
//tmp[i]统计i的子树点权和。f[i]第i个连通分量是否有非桥边。flag整个图中是否有桥。 
//sum总点权。scc[0]统计scc总数。scc[i]计算第i个scc点权和 。 
struct edge{
    int to,next;
}e[2*N];
void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
    return;
}
void Tarjan(int u,int fr){
    dfn[u]=low[u]=++cnt;
    scc[scc[0]]+=w[u],tmp[u]=w[u];
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(!dfn[v]){
            Tarjan(v,u);
            low[u]=min(low[u],low[v]);
            tmp[u]+=tmp[v];//累加子树点权。 
            if(dfn[u]<low[v]){
                flag=1;
                ans=min(ans,abs(sum-2*tmp[v])); 
            }//找到桥，更新若仅一个scc时答案。
        }else if(v!=fr){
            low[u]=min(low[u],dfn[v]);
            f[scc[0]]=1; //存在非桥边 。
        }
    }
    return;
}
signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&w[i]);
        sum+=w[i];
    }
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%lld%lld",&u,&v);
        add(u,v),add(v,u);
    }
    cnt=0;
    for(int i=1;i<=n;i++){
        if(!dfn[i]){
            scc[0]++;
            Tarjan(i,0);
        }
    }
    if(scc[0]>=3){//scc多于两个，无解。 
        printf("-1");
    }else if(scc[0]==2){
        if(f[1] || f[2]){//scc=2且存在非桥边。 
            printf("%lld",abs(scc[2]-scc[1]));
        }else{
            printf("-1");
        }
    }else{
        if(!flag){//仅1个scc且不存在桥，无解。 
            printf("-1");
        }else{
            printf("%lld",ans);
        }
    }
    return 0;
}

若有错误请指出。

题解：P9424 [蓝桥杯 2023 国 B] 删边问题

题意

思路

一些细节

Code