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

直接套次小生成树的板子

看一下和最小生成树是不是相同就可以了

#include 
   
    #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];struct p{
   	int l,r,w;}a[maxn<<2];bool com(p a,p b){
   	return a.w < b.w ;}struct edge{
   	int to,nxt,w;}d[maxn<<2]; int head[maxn<<2],cnt=1;void add(int u,int v,int w){
   d[++cnt] = (edge){
   v,head[u],w},head[u]=cnt;}int find(int x){
    return x==pre[x]?x:pre[x]=find(pre[x]);}int kur(){
   	sort(a+1,a+1+m,com);	for(int i=1;i<=n;i++)	pre[i]=i;	int ans=0;	for(int i=1,j=1;i
     
      =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,maxx[x][i] );			ans = max(ans,maxx[y][i] );			x=fa[x][i],y=fa[y][i];		}	ans = max(ans,maxx[x][0] );	ans = max(ans,maxx[y][0] );	return ans;}void init(){
   	cnt=1;	for(int i=1;i<=m;i++)	ok[i]=0;	for(int i=0;i<=n;i++)	head[i]=0;	for(int i=1;i<=n;i++)		lg[i] = lg[i-1]+((1<
      
       > t;	while( t-- )	{
   			cin >> n >> m;		init();		for(int i=1;i<=m;i++)			cin >> a[i].l >> a[i].r >> a[i].w;		int chu = kur();		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 );		}		if( chu!=ans||ans==inf )	cout << chu << endl;		else	cout << "Not Unique!\n" ;	}}
      
     
    
   

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