新浪国际足球新闻,曹操煮酒论英雄,冰封夕阳去哪了
我们已经熟知了求最小生成树的方法,用kruskal,prim算法都可以搞
那么我们如何求次小生成树呢?
这里次小生成树的定义是
边权和严格大于最小生成树的边权和最小的生成树
次小生成树嘛,肯定和最小生成树脱不了关系
那么我们首先求出最小生成树
接下来,一个比较显然的思路是
枚举每一条未加入最小生成树的边,加入最小生成树,同时在最小生成树中删除边权最大的边
如果你想到了这里并写出了代码,那么恭喜你
你在里成功还有一步之遥成功掉进坑里了
比如下面的例子
蓝边表示最小生成树中的边,黄边表示新加入的边
在这种情况下,如果仅仅记录最大值的话,得到的答案一定是错的
所以我们还要记录严格小于最大值的最大值
当产生冲突的时候我们需要删除严格小于最大值的最大值
但是这样效率太低了,每一次查询都是\(O(n)\)的
有没有更好的方法呢?
不要忘了,最小生成树它是一棵树呀
树的链上最大最小值操作,你想到了什么?
没错!树上倍增
我们在倍增的过程中记录下最大值和严格小于最大值的最大值
这样每次查询的复杂度就变成\(log(n)\)啦
整个算法的流程大概是
用kruskal是\(O(m\log m+Q\log (n))\)
用prim是\(O(n\log n+Q\log (n))\)
Q为询问次数
放一道裸题
// luogu-judger-enable-o2 #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<iostream> #define int long long using namespace std; const int MAXN=400001; const int INF=1e15+10; inline int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } struct Edge { int u,v,w; }E[MAXN]; int Enum=1; void Add(int x,int y,int z) { E[Enum].u=x; E[Enum].v=y; E[Enum].w=z;Enum++; } struct node { int u,v,w,nxt; }edge[MAXN]; int head[MAXN]; int num=1; int N,M; int fa[MAXN],vis[MAXN],sum; int deep[MAXN],f[MAXN][21],maxx[MAXN][21],minx[MAXN][21]; void AddEdge(int x,int y,int z) { edge[num].u=x; edge[num].v=y; edge[num].w=z; edge[num].nxt=head[x]; head[x]=num++; } int find(int x) { if(fa[x]==x) return fa[x]; else return fa[x]=find(fa[x]); } int unionn(int x,int y) { int fx=find(x),fy=find(y); fa[fx]=fy; } int comp(const Edge &a,const Edge &b) { return a.w<b.w; } void Kruskal() { sort(E+1,E+Enum,comp); int tot=0; for(int i=1;i<=Enum-1;i++) { int x=E[i].u,y=E[i].v; if(find(x)!=find(y)) { unionn(x,y),tot++,sum+=E[i].w,vis[i]=1; AddEdge(x,y,E[i].w);AddEdge(y,x,E[i].w); } if(tot==N-1) break; } } void dfs(int now,int fa) { for(int i=head[now];i!=-1;i=edge[i].nxt) { if(edge[i].v==fa) continue; deep[edge[i].v]=deep[edge[i].u]+1; f[edge[i].v][0]=now; maxx[edge[i].v][0]=edge[i].w; dfs(edge[i].v,now); } } void pre() { for(int i=1;i<=18;i++) { for(int j=1;j<=N;j++) { f[j][i]=f[ f[j][i-1] ][i-1]; maxx[j][i]=max(maxx[j][i-1],maxx[ f[j][i-1] ][i-1]); minx[j][i]=max(minx[j][i-1],minx[ f[j][i-1] ][i-1]); if(maxx[j][i-1]>maxx[ f[j][i-1] ][i-1]) minx[j][i]=max(minx[j][i],maxx[ f[j][i-1] ][i-1]); else minx[j][i]=max(minx[j][i],maxx[j][i-1]); } } } int LCA(int x,int y) { if(deep[x]<deep[y]) swap(x,y); for(int i=18;i>=0;i--) if(deep[ f[x][i] ] >= deep[y] ) x=f[x][i]; if(x==y) return x; for(int i=18;i>=0;i--) if(f[x][i] != f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0]; } int findmax(int x,int lca,int val) { int ans=0; for(int i=18;i>=0;i--) { if(deep[ f[x][i] ] >= deep[lca]) { if(maxx[x][i]==val) ans=max(ans,minx[x][i]); else ans=max(ans,maxx[x][i]); x=f[x][i]; } } return ans; } void work() { int ans=INF; for(int i=1;i<=Enum-1;i++) { if(vis[i]) continue; int x=E[i].u,y=E[i].v,z=E[i].w; int lca=LCA(x,y); int lmx=findmax(x,lca,z); int rmx=findmax(y,lca,z); if(max(lmx,rmx)!=z) ans=min(ans,sum+z-max(lmx,rmx)); } printf("%lld",ans); } main() { #ifdef WIN32 freopen("a.in","r",stdin); #else #endif N=read(),M=read(); memset(head,-1,sizeof(head)); for(int i=1;i<=N;i++) fa[i]=i; for(int i=1;i<=M;i++) { int x=read(),y=read(),z=read(); Add(x,y,z); } Kruskal(); deep[1]=1; dfs(1,0); pre(); work(); return 0; }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论