Kruskal 重构树 · ooliver

P2245 星际导航这是一道模板题，借这道模板解释 Kruskal 重构树的构造与作用。定义 Kruskal 重构树是基于 Kruskal 的最小生成树算法在无向图中得出的树所构造而成的树。构造上图是样例上图是样例的最小生成树 C++ void ks(){ for(int i=1;i `void ks(){ for(int i=1;in;i++) fa[i]=i; sort(e+1,e+m+1); cn=n; for(int i=1;im;i++){ int x=find(e[i].u),y=find(e[i].v); if(x!=y){ fa[x]=fa[y]=++cn,fa[cn]=cn,w[cn]=e[i].w; g[cn].push_back(x),g[cn].push_back(y); } } }` 以上是构造 Kruskal 重构树的代码。不难发现，其核心是在按边排序后用一个新点链接两点，并作为并查集的代表。以上就是根据样例构造出的 Kruskal 重构树，括号中的表示点权。性质一颗二叉树是大根堆（最小生成树的基础上）原图中两个点间所有路径上的边最大权值的最小值 = 最小生成树上两点简单路径的边最大权值 = Kruskal 重构树上两点 LCA 的点权。那么根据这个性质，这道模板题就做出来了。代码： C++ #include using namespace std; #define int long long const int N=3e5+5; struct node{ int u,v,w; bool operator g[N]; int n,m,q,cn; int fa[N],w[N],up[N][20],dep[N]; int find(int x){ if(x==fa[x]) return x; return fa[x]=find(fa[x]); } void ks(){ for(int i=1;i=0;i--){ if(dep[up[x][i]]>=dep[y]) x=up[x][i]; } if(x==y) return x; for(int i=19;i>=0;i--){ if(up[x][i]!=up[y][i]){ x=up[x][i],y=up[y][i]; } } return up[x][0]; } signed main(){ cin>>n>>m; for(int i=1;i>e[i].u>>e[i].v>>e[i].w; } ks(); for(int i=1;i>q; while(q--){ int x,y; cin>>x>>y; if(find(x)!=find(y)) cout `#include using namespace std; #define int long long const int N=3e5+5; struct node{ int u,v,w; bool operator const node &a)const{ return wa.w; } }e[N]; vectorint> g[N]; int n,m,q,cn; int fa[N],w[N],up[N][20],dep[N]; int find(int x){ if(x==fa[x]) return x; return fa[x]=find(fa[x]); } void ks(){ for(int i=1;in;i++) fa[i]=i; sort(e+1,e+m+1); cn=n; for(int i=1;im;i++){ int x=find(e[i].u),y=find(e[i].v); if(x!=y){ fa[x]=fa[y]=++cn,fa[cn]=cn,w[cn]=e[i].w; g[cn].push_back(x),g[cn].push_back(y); } } } void dfs(int u,int f){ up[u][0]=f,dep[u]=dep[f]+1; for(int i=1;i19;i++) up[u][i]=up[up[u][i-1]][i-1]; for(int v:g[u]){ if(v==f) continue; dfs(v,u); } } int lca(int x,int y){ if(dep[x]dep[y]) swap(x,y); for(int i=19;i>=0;i--){ if(dep[up[x][i]]>=dep[y]) x=up[x][i]; } if(x==y) return x; for(int i=19;i>=0;i--){ if(up[x][i]!=up[y][i]){ x=up[x][i],y=up[y][i]; } } return up[x][0]; } signed main(){ cin>>n>>m; for(int i=1;im;i++){ cin>>e[i].u>>e[i].v>>e[i].w; } ks(); for(int i=1;icn;i++){ if(i==fa[i]) dfs(i,0); } cin>>q; while(q--){ int x,y; cin>>x>>y; if(find(x)!=find(y)) cout"impossible\n"; else coutw[lca(x,y)]"\n"; } return 0; }` P1967 [NOIP 2013 提高组] 货车运输这道题和模板基本一样，只不过要求的是两点间所有路径上边的最小值的最大值，和上题相反，要用最大生成树。这里取个巧，把边权变负，直接套模板，输出时再变正即可。代码： C++ #include using namespace std; #define int long long const int N=3e5+5; struct node{ int u,v,w; bool operator g[N]; int n,m,q,cn; int fa[N],w[N],up[N][20],dep[N]; int find(int x){ if(x==fa[x]) return x; return fa[x]=find(fa[x]); } void ks(){ for(int i=1;i=0;i--){ if(dep[up[x][i]]>=dep[y]) x=up[x][i]; } if(x==y) return x; for(int i=19;i>=0;i--){ if(up[x][i]!=up[y][i]){ x=up[x][i],y=up[y][i]; } } return up[x][0]; } signed main(){ cin>>n>>m; for(int i=1;i>e[i].u>>e[i].v>>e[i].w; e[i].w=-e[i].w; } ks(); for(int i=1;i>q; while(q--){ int x,y; cin>>x>>y; if(find(x)!=find(y)) cout `#include using namespace std; #define int long long const int N=3e5+5; struct node{ int u,v,w; bool operator const node &a)const{ return wa.w; } }e[N]; vectorint> g[N]; int n,m,q,cn; int fa[N],w[N],up[N][20],dep[N]; int find(int x){ if(x==fa[x]) return x; return fa[x]=find(fa[x]); } void ks(){ for(int i=1;in;i++) fa[i]=i; sort(e+1,e+m+1); cn=n; for(int i=1;im;i++){ int x=find(e[i].u),y=find(e[i].v); if(x!=y){ fa[x]=fa[y]=++cn,fa[cn]=cn,w[cn]=e[i].w; g[cn].push_back(x),g[cn].push_back(y); } } } void dfs(int u,int f){ up[u][0]=f,dep[u]=dep[f]+1; for(int i=1;i19;i++) up[u][i]=up[up[u][i-1]][i-1]; for(int v:g[u]){ if(v==f) continue; dfs(v,u); } } int lca(int x,int y){ if(dep[x]dep[y]) swap(x,y); for(int i=19;i>=0;i--){ if(dep[up[x][i]]>=dep[y]) x=up[x][i]; } if(x==y) return x; for(int i=19;i>=0;i--){ if(up[x][i]!=up[y][i]){ x=up[x][i],y=up[y][i]; } } return up[x][0]; } signed main(){ cin>>n>>m; for(int i=1;im;i++){ cin>>e[i].u>>e[i].v>>e[i].w; e[i].w=-e[i].w; } ks(); for(int i=1;icn;i++){ if(i==fa[i]) dfs(i,0); } cin>>q; while(q--){ int x,y; cin>>x>>y; if(find(x)!=find(y)) cout"-1\n"; else coutw[lca(x,y)]"\n"; } return 0; }`