自动搬运

查看原文

来自洛谷，原作者为

	lenlen 一如既往，萬事勝意.

搬运于2025-08-24 22:08:31，当前版本为作者最后更新于2023-02-09 17:06:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前言:好多题解被 hack 了啊。

Problem

题目大意：给定一张图，$A$ 先添加 $1$ 条边，$B$ 再删去一条边使得图不连通，$A$ 要最大化删除边的权值，$B$ 要最小化删除边的权值，问最终的权值是多少。

数据范围： $n \leq 5 \times 10^5,m \leq 10^6$。

Solution

前置芝士：边双连通分量。

显然，边双中的边是肯定不能删的，因为删除了也并不会使图不连通。所以我们有个自然的想法，我们可以把边双缩点，在重新建图，这样我们就简化为了树上问题。

然后我们考虑树上怎么做，想一想会发现，$A$ 的操作链接 $i,j$ 等价于将树上 $i,j$ 缩点之后的编号 $i',j'$ 链上的边去掉了，因为加边后这条链会构成一个边双，删除边双中的任意一个点都是无法使图不连通的，这个很显然。

然后我们可以考虑，从小到大枚举每一条边，看看枚举的这条边和之前的边能否构成一条链，如果不能构成那么显然这条边就是答案，否则若所有边都可以构成一条链，那么输出 $-1$ 即可。

至于如何判断能否构成链，可以发现，我们以最小的边的任意一个端点作为根节点，那么除了根节点，显然每一个点只能有一个点作为它的儿子，若新加边的端点往上跳，若跳到一个点有儿子且不是自己，那么就够不成链。根节点要特判一下。

至于时间复杂度，本来我想用倍增的，但是我们可以发现，每一个点只会被更新一次，更新第二次要么直接退出（即发现构不成链），或者不用往上跳了（显然，当前节点满足，祖先节点显然不影响）。所以暴力跳是均摊的复杂度，是比非均摊的倍增还快的。

结合代码感性理解一下哈！

截止 $2023.2.9$，暂时过了所有 hack。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+7232;
int n,m,x,y,z;
struct hl{
	int v,nxt,w;
}e[N];
struct len{
	int u,v,w;
}t[N];
int h[N],cnt=1;
bitset<N> vis;
void add(int u,int v,int w)
{
	e[++cnt].v=v;e[cnt].nxt=h[u];h[u]=cnt;e[cnt].w=w;
}
int mi(int x,int y){return x<y?x:y;}
int dfn[N],low[N],tot,now;
void tarjan(int x,int fx)
{
	dfn[x]=low[x]=++tot;
	for(int i=h[x];i;i=e[i].nxt)
	{
		if(e[i].v==fx) continue;
		if(!dfn[e[i].v])
		{
			tarjan(e[i].v,x);
			low[x]=mi(low[x],low[e[i].v]);
			if(low[e[i].v]>dfn[x]) vis[i]=vis[i^1]=1;
		}
		else low[x]=mi(low[x],dfn[e[i].v]);
	}
}
int ecc[N];
void dfs(int x)
{
	ecc[x]=now;
	for(int i=h[x];i;i=e[i].nxt)
	{
		if(vis[i]||ecc[e[i].v]) continue;
		dfs(e[i].v);
	}
}
bool cmp(len x,len y)
{
	return x.w<y.w;
}
int fa[N],dis[N],dep[N],son;
void dfss(int x,int fx)
{
	fa[x]=fx;dep[x]=dep[fx]+1;
	for(int i=h[x];i;i=e[i].nxt)
	{
		if(e[i].v==fx) continue;
		dfss(e[i].v,x);
 	}
}
int num;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);add(y,x,z);
		t[i]={x,y,z};
	}
	for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i,i);
	for(int i=1;i<=n;i++) if(!ecc[i]) ++now,dfs(i);//找边双
	memset(h,0,sizeof(h));cnt=0;
	for(int i=1;i<=m;i++)
		if(ecc[t[i].u]!=ecc[t[i].v]) add(ecc[t[i].u],ecc[t[i].v],t[i].w),add(ecc[t[i].v],ecc[t[i].u],t[i].w),t[++num]=t[i];
	//重新加边
	sort(t+1,t+num+1,cmp);
	dfss(ecc[t[1].u],0);dis[ecc[t[1].u]]=ecc[t[1].v];//以最小的边的一个端点作为根
	for(int i=2;i<=num;i++)
	{
		int k=dep[ecc[t[i].u]]>dep[ecc[t[i].v]]?ecc[t[i].u]:ecc[t[i].v];//从深度深的跳
		while(!dis[fa[k]]) dis[fa[k]]=k,k=fa[k];//跳到一个固定儿子的点
		if(son==0&&fa[k]==ecc[t[1].u]&&dis[fa[k]]!=k) son=k;//若为根，特判
		else if(dis[fa[k]]==k||fa[k]==ecc[t[1].u]&&son==k) ;//若当前节点的父亲在链上的儿子就是自己，那么退出
		else //否则输出边的权值
		{
			printf("%d\n",t[i].w);
			return 0;
		}
	}
	printf("-1\n");
}