本文共 1963 字，大约阅读时间需要 6 分钟。

题意

​ 给定一张 n 个点 m 条边的无向连通图

加入一条边，使得图中权值最小的桥权值最大，如果能使图中没有桥则输出 −1。

首先环内的边删去没有用处,所以边双连通缩成一棵树

那么在树上两点连接,路径上的边都不是桥了

问题转化为,在树上选择一条链,使得其余边的最小边权最大.

那么树上的最小边一定在链上

那么这棵树被这条特殊边分成两棵树,可以分别以边的两端向下延伸

而且每到一个点,维护向下走的最小值和次小值

那么这条路径最多覆盖最小值,次小值不可避免,取$min$即可

#include 
   
    using namespace std;const int maxn = 4e5+10;const int inf = 1e9;const int INF = 1e9;struct edge{
   	int u,to,nxt,w;}d[maxn]; int head[maxn],cnt=1;void add(int u,int v,int w){
    d[++cnt] = (edge){
   u,v,head[u],w},head[u] = cnt; }int n,m;int low[maxn],stac[maxn],vis[maxn],dfn[maxn],bcc[maxn],id,top,bccn;void tarjan(int u,int fa){
   	bool flag = 0;	dfn[u] = low[u] = ++id, stac[++top] = u, vis[u] = 1;	for(int i=head[u];i;i=d[i].nxt )	{
   		int v = d[i].to;		if( !dfn[v] )		{
   			tarjan(v,u);			low[u] = min( low[u],low[v] ); 		}		else if( vis[v] )		{
   			if( v!=fa || flag )				low[u] = min( low[u],dfn[v] );			else	flag = 1;//如果第一次经过fa,标记是重边 		}	}	if( low[u]==dfn[u] )	{
   		int temp; bccn++;		while( temp = stac[top--] )		{
   			vis[temp] = 0, bcc[temp] = bccn;			if( temp==u )	break;		}	}}typedef pair
    
     p;vector
     
vec[maxn];void init(){
   	cnt = 1, bccn=id=top=0;	for(int i=1;i<=n;i++)	{
   		low[i]=dfn[i]=head[i]=vis[i]=stac[i]=bcc[i]=0;		vec[i].clear();	}}int U,V,ans;int dfs(int u,int fa){
   	int mi2=1e9,mi1=1e9;	for(auto s:vec[u] )	{
   		int v = s.first, w = s.second;		if( v==fa )	continue;		int nxt = min( w,dfs(v,u) );		if( nxt
      
       > n >> m )	{
   		for(int i=1;i<=m;i++)		{
   			int l,r,w; cin >> l >> r >> w;			if( l>n || r>n )	continue;			add(l,r,w); add(r,l,w);		}		for(int i=1;i<=n;i++)			if( !dfn[i] )	tarjan(i,i);		int minn = 1e9;		U = 0,V = 0;		for(int i=2;i<=cnt;i++)		{
   			int u = d[i].u, v = d[i].to;			if( bcc[u]!=bcc[v] )			{
   				vec[bcc[u]].push_back( p(bcc[v],d[i].w) );				if( minn>d[i].w )					minn = d[i].w, U = bcc[u], V = bcc[v];			}		}		ans = inf; dfs(U,V); dfs(V,U);		if( ans==1e9 )	ans = -1;		cout << ans << endl;		init();	}}
      
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/110041048 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！