自动搬运

查看原文

来自洛谷，原作者为

	BitByBit a.k.a. 海绵猴子

搬运于2025-08-24 22:48:14，当前版本为作者最后更新于2025-03-27 09:04:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

AC记录

题意

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

定义

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

（引用自 OI wiki）

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

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

分析

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

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

判断无解：

• 如果原图有且只有一个双连通分量就无解；
• 如果原图有两个连通分量，则只能在双连通分量中删边，所以判断是不是所有双连通分量点数都为 $1$，是则无解，否则求出两个连通分量的权值和的差；
• 如果原图有 $3$ 个或更多连通分量，显然无解。

程序

#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);
}