题目要求割掉一条边后使得图不连通,那么可以使用tarjan算法求出所有的割边,然后把边双缩成点,就能得到一棵树,现在问题是在加入一条边的情况下,割掉最小的一条边使得图不连通,割掉的这条边权值最大是多少
加入的边如果是\((x,y)\),就可以使得链\((x,y)\)上所有边不被割,要最大化答案就要让比答案小的边都在一条链上,所以可以从小到大加入树边,如果加到某一时刻这些边不能在同一条链上那么也就能得到答案
我们可以维护加入边构成的链,可以利用求lca以及书上距离等方法维护,一些说明详见代码口胡警告
#include<bits/stdc++.h>
#define LL long long
#define db long double
#define il inline
#define re register
#define mkpr make_pair
using namespace std;
const int N=500000+10;
il int rd()
{
int x=0,w=1;char ch=0;
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int to[N<<1],nt[N<<1],w[N<<1],hd[N],tot=1;
void add(int x,int y,int z)
{
++tot,to[tot]=y,nt[tot]=hd[x],w[tot]=z,hd[x]=tot;
++tot,to[tot]=x,nt[tot]=hd[y],w[tot]=z,hd[y]=tot;
}
int n,m;
int dfn[N],low[N],ti,po[N];
int fa[N],sz[N],de[N],hs[N],top[N];
void dfs1(int x)
{
sz[x]=1;
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(y==fa[x]) continue;
fa[y]=x,de[y]=de[x]+1,dfs1(y),sz[x]+=sz[y];
hs[x]=sz[hs[x]]>sz[y]?hs[x]:y;
}
}
void dfs2(int x,int ntp)
{
dfn[x]=++ti,top[x]=ntp;
if(hs[x]) dfs2(hs[x],ntp);
for(int i=hd[x];i;i=nt[i])
{
int y=to[i];
if(y!=fa[x]&&y!=hs[x]) dfs2(y,y);
}
}
int glca(int x,int y)
{
while(top[x]!=top[y])
{
if(de[top[x]]<de[top[y]]) swap(x,y);
x=fa[top[x]];
}
return de[x]<de[y]?x:y;
}
int gdis(int x,int y){return de[x]+de[y]-(de[glca(x,y)]<<1);}
bool brg[N];
void tj(int x,int ffa)
{
dfn[x]=low[x]=++ti;
for(int i=hd[x];i;i=nt[i])
{
if(i==ffa) continue;
int y=to[i];
if(!dfn[y])
{
tj(y,i^1),low[x]=min(low[x],low[y]);
if(dfn[x]<low[y]) brg[i>>1]=1;
}
else low[x]=min(low[x],dfn[y]);
}
}
int findf(int x){return po[x]==x?x:po[x]=findf(po[x]);}
struct edge
{
int x,y,z;
edge(){}
edge(int nx,int ny,int nz){x=nx,y=ny,z=nz;if(de[x]>de[y]) swap(x,y);}
bool operator < (const edge &bb) const {return z<bb.z;}
}e[N];
int main()
{
n=rd(),m=rd();
for(int i=1;i<=m;++i)
{
int x=rd(),y=rd(),z=rd();
add(x,y,z);
}
tj(1,0);
for(int i=1;i<=n;++i) po[i]=i;
for(int i=1;i<=m;++i)
if(!brg[i]) po[findf(to[i<<1])]=findf(to[i<<1|1]);
memset(hd,0,sizeof(hd)),tot=1;
for(int i=1;i<=m;++i)
if(findf(to[i<<1])!=findf(to[i<<1|1])) add(findf(to[i<<1]),findf(to[i<<1|1]),w[i<<1]);
m=tot>>1;
ti=0,dfs1(findf(1)),dfs2(findf(1),findf(1));
for(int i=1;i<=m;++i) e[i]=(edge){to[i<<1],to[i<<1|1],w[i<<1]};
sort(e+1,e+m+1);
int x=e[1].y,y=0,z=e[1].x; //x,y为链的两端点,z为链深度最浅的点
for(int i=2;i<=m;++i)
{
int xx=e[i].x,yy=e[i].y; //分别表示加入边深度浅的点和深度深的点
if(!y) //链是直上直下的
{
if(dfn[yy]>=dfn[x]&&dfn[yy]<=dfn[x]+sz[x]-1) x=yy; //新的下端点要在当前下端点子树内
else if(glca(z,yy)==yy) z=xx; //新的上端点要是当前上端点的祖先
else
{
int p1=glca(x,xx),p2=glca(z,xx);
if(p1!=p2) return printf("%d\n",e[i].z),0; //加入的边从链的中间分岔出去,不合法
if(gdis(x,xx)!=gdis(x,yy)+gdis(yy,xx)) y=yy,z=glca(x,y); //从链顶分叉出去,形成一上一下的链
}
}
else //一上一下的链
{
if(dfn[yy]>=dfn[x]&&dfn[yy]<=dfn[x]+sz[x]-1) x=yy;
else if(dfn[yy]>=dfn[y]&&dfn[yy]<=dfn[y]+sz[y]-1) y=yy; //新的端点要在原端点的子树内
else if(gdis(x,y)!=gdis(x,xx)+gdis(xx,y)||gdis(x,y)!=gdis(x,yy)+gdis(yy,y)) return printf("%d\n",e[i].z),0; //如果某个点不在路径上就不合法
}
}
puts("-1");
return 0;
}