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

题意

给定一个无向图

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

CPP

#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

相关推荐

评论

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