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

· · 题解

AC记录

题意

有一个无向图，点有点权，删去一条边，将其分成两个连通分量，问两个连通分量点权之和的差的绝对值最小是多少。

定义

边双连通分量：在一张连通的无向图中，对于两个点 x 和 y，如果无论删去哪条边（只能删去一条）都不能使它们不连通，我们就说 x 和 y 边双连通。对于一个无向图中的极大边双连通的子图，我们称这个子图为一个边双连通分量。

（引用自 OI wiki）

下文中双连通分量指边双。

连通分量不一定是双连通分量。

分析

首先考虑树的情况：在树上任意删掉一条边就可以分成两个连通分量。所以只要一遍 DFS 求出子树大小然后对每个点求子树和其余的差的绝对值的最小值即可。

那不是数怎么办？可以缩点。用 Tarjan 找出双连通分量然后缩点，图就变成树了。然后就和上面一样了。

判断无解：

程序

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=200010,M=400010;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll n,m,ans;
ll tot,dfn,cnt,top,tot1;
ll Val[N],Son[M],Next[M],Head[N];
ll Dfn[N],Low[N],Stk[N],Vis[N],Scc[N],Size[N],Cnt[N];
ll Son1[M],Next1[M],Head1[N],Size1[N],Vis1[N];
inline void add(ll x,ll y)//原图建边
{
    Son[++tot]=y;
    Next[tot]=Head[x];
    Head[x]=tot;
}
inline void add1(ll x,ll y)//缩点后新图建边
{
    Son1[++tot1]=y;
    Next1[tot1]=Head1[x];
    Head1[x]=tot1;
}
void Tarjan(ll x,ll f)//Tarjan求BCC
{
    Dfn[x]=Low[x]=++dfn;
    Stk[++top]=x;
    Vis[x]=1;
    for(ll i=Head[x];i;i=Next[i])
    {
        ll y=Son[i];
        if(i==((f-1)^1)+1)continue;
        if(!Dfn[y])
        {
            Tarjan(y,i);
            Low[x]=min(Low[x],Low[y]);
        }
        else if(Vis[y])
            Low[x]=min(Low[x],Dfn[y]);
    }
    if(Dfn[x]==Low[x])
    {
        cnt++;
        while(1)
        {
            ll y=Stk[top];
            top--;
            Scc[y]=cnt;//其实是BCC不是SCC
            Cnt[cnt]++;
            Size[cnt]+=Val[y];
            Vis[y]=0;
            if(x==y)break;
        }
    }
}
void dfs(ll x,ll f)//dfs求子树大小
{
    Size1[x]=Size[x];
    for(ll i=Head1[x];i;i=Next1[i])
    {
        ll y=Son1[i];
        if(y==f)continue;
        Vis1[y]=1;
        dfs(y,x);
        Size1[x]+=Size1[y];
    }
}
int main()
{
    ll x,y;
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&Val[i]);
    for(ll i=1;i<=m;i++)
    {
        scanf("%lld%lld",&x,&y);
        add(x,y);
        add(y,x);
    }
    ll k=0;
    for(ll i=1;i<=n;i++)
        if(!Dfn[i])
        {
            Tarjan(i,0);
            k++;
            if(k>=3)return printf("-1"),0;
        }
    if(k==2)
    {
        bool flag=0;
        for(ll i=1;i<=cnt;i++)
            if(Cnt[i]>=2)
                flag=1;
        if(!flag)return printf("-1"),0;
        dfs(1,0);
        for(ll i=1;i<=cnt;i++)
            if(!Vis1[i])
            {
                dfs(i,0);
                printf("%lld",abs(Size1[1]-Size1[i]));
                break;
            }
        return 0;
    }
    if(cnt==1)return printf("-1"),0;
    for(ll i=1;i<=n;i++)
        for(ll j=Head[i];j;j=Next[j])
            if(Scc[i]!=Scc[Son[j]])
                add1(Scc[i],Scc[Son[j]]);//缩点
    dfs(1,0);
    ans=inf;
    for(ll i=1;i<=cnt;i++)
        ans=min(ans,abs(Size1[1]-Size1[i]-Size1[i]));
    printf("%lld",ans);
}