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

有定理

存在次小生成树,只替换最小生成树的一条边得来。

那么先跑一遍最小生成树

然后枚举不在树边的边$(u,v)$

假如加入这条边,树就会成环,我们需要删掉$u->v$的一条树边

显然删掉最大的那条边最优秀

这个过程使用$LCA$来优化

带权$LCA$

#include 
   
    using namespace std;#define int long longconst int maxn=2e5+10; const int inf=1e18;int n,m;int pre[maxn],deep[maxn],lg[maxn],ok[maxn];int fa[maxn][21],maxx[maxn][21],ci[maxn][21];struct p{
   	int l,r,w;	bool operator < (const p&tmp ){
   		return w
    
     maxx[r][i-1] )				ci[u][i] = max( ci[u][i],maxx[r][i-1] );		else if( maxx[u][i-1]
     
      =0;i--)		if( deep[fa[x][i]]>=deep[y] )		{
   			if( w!=maxx[x][i] )	ans = max(ans,maxx[x][i] );			else	ans = max(ans,ci[x][i] );			x = fa[x][i];		}	if( x==y )	return ans;	for(int i=20;i>=0;i--)		if( fa[x][i]!=fa[y][i] )		{
   				if( w!=maxx[x][i] )	ans = max(ans,maxx[x][i] );			else	ans = max(ans,ci[x][i] );			if( w!=maxx[y][i] )	ans = max(ans,maxx[y][i] );			else	ans = max(ans,ci[y][i] );			x=fa[x][i],y=fa[y][i];		}	if( w!=maxx[x][0] )	ans = max(ans,maxx[x][0] );	else	ans = max(ans,ci[x][0] );	if( w!=maxx[y][0] )	ans = max(ans,maxx[y][0] );	else	ans = max(ans,ci[y][0] );		return ans;}void init(){
   	for(int i=1;i<=n;i++)		lg[i] = lg[i-1]+((1<
      
       > n >> m;	init();	for(int i=1;i<=m;i++)		cin >> a[i].l >> a[i].r >> a[i].w;	int chu = kur();	ci[1][0]=-inf;	dfs(1,0);	int ans = inf;	for(int i=1;i<=m;i++)	{
   		if( ok[i] )	continue;		int u = a[i].l,v = a[i].r, w = a[i].w;		ans = min( ans,chu-LCA(u,v,w)+w );	}	cout << ans;}
      
     
    
   

先求$lca$再跳,其实都差不多

#include 
   
    using namespace std;#define int long longconst int maxn=2e5+10; const int inf=1e18;int n,m;int pre[maxn],deep[maxn],lg[maxn],ok[maxn];int fa[maxn][21],maxx[maxn][21],ci[maxn][21];struct p{
   	int l,r,w;	bool operator < (const p&tmp ){
   		return w
    
     maxx[r][i-1] )				ci[u][i] = max( ci[u][i],maxx[r][i-1] );		else if( maxx[u][i-1]
     
      =0;i--)		if( deep[fa[x][i]]>=deep[y] )	x=fa[x][i];	if( x==y )	return x;	for(int i=20;i>=0;i--)		if( fa[x][i]!=fa[y][i] )				x=fa[x][i],y=fa[y][i];	return fa[x][0];}int make_max(int x,int y,int da){
   	int ans = -inf;	for(int i=20;i>=0;i--)		if( deep[fa[x][i]]>=deep[y] )		{
   			if( da!=maxx[x][i] )	ans =max( ans,maxx[x][i] );			else	ans = max( ans,ci[x][i] );			x = fa[x][i];		}	return ans;}void init(){
   	for(int i=1;i<=n;i++)		lg[i] = lg[i-1]+((1<
      
       > n >> m;	init();	for(int i=1;i<=m;i++)		cin >> a[i].l >> a[i].r >> a[i].w;	int chu = kur();	ci[1][0]=-inf;	dfs(1,0);	int ans = inf;	for(int i=1;i<=m;i++)	{
   		if( ok[i] )	continue;		int u = a[i].l,v = a[i].r, w = a[i].w;		int lca = LCA(u,v);		int q=make_max(u,lca,w), e = make_max(v,lca,w);		ans = min( ans,chu-max(q,e)+w );	}	cout << ans;}
      
     
    
   

非严格次小生成树

#include 
   
    #include 
    
     #include 
     
      #include 
      
       using namespace std;const int maxn = 2e5+10;const int inf = 1e9;struct p{
   	int l,r,w;	bool operator < (const p&tmp )	const{
   		return w
       
        =0;i--)		if( deep[fa[x][i]]>=deep[y] )		{
   			ans = max( ans,maxx[x][i] );			x = fa[x][i];		}	if( x==y )	return ans;	for(int i=20;i>=0;i--)		if( fa[x][i]!=fa[y][i] )		{
   			ans = max( ans,max(maxx[x][i],maxx[y][i]) );			x = fa[x][i], y = fa[y][i];		}	ans = max( ans,max( maxx[x][0],maxx[y][0]) );	return ans;}void init(){
   	for(int i=1;i<=m;i++)	ok[i] = 0;	cnt = 1;	for(int i=1;i<=n;i++)	head[i] = 0;}int main(){
   	int T; cin >> T;	while( T-- )	{
   		scanf("%d%d",&n,&m);		for(int i=1;i<=m;i++)			cin >> a[i].l >> a[i].r >> a[i].w;		int chu = kur(),ans = inf;		dfs(1,0);		for(int i=1;i<=m;i++)		{
   			if( ok[i] )	continue;			ans = min( ans , chu-lca(a[i].l,a[i].r)+a[i].w );		}//		if( chu==ans )	cout << "Not Unique!\n";//		else	cout << chu << endl;		init();	}}
       
      
     
    
   

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