文章目录

Kruskal算法Kruskal重构树定义性质 例题两道板子题一道令人愉悦的树套树

Kruskal算法

众所周知，Kruskal是一种优秀的基于并查集的最小（最大）生成树算法。它的简要流程为：

将所有边按边权排序；依次枚举所有边的两端点$u$和$v$，若它们不在一个联通块内，则将该边加入生成树的边集中，且将$u$、$v$合并于一个连通块中。

Kruskal重构树

定义

Kruskal重构树的定义（构造方式）：

一开始，各个结点都在一个以自己为根的连通块中；执行Kruskal算法，重复以下步骤： 把即将加入生成树边集的边，看做一个新点$x$，$x$的两儿子分别是$u$所在的连通块对应的根和$v$所在的连通块对应的根，$x$的点权是该边的边权；合并$u$、$v$，这个合并后的连通块的根是$x$。

---

举个建树的例子（数据来自于BZOJ3545 [ONTAK2010]Peaks）： 注意，最开始的叶子结点的顺序不重要，这里为了好看，重新排列了一下。

性质

于是Kruskal重构树的定义就弄清楚了。 下面这个不是动图：

接下来看一下这个东西的性质（接下来只探讨最小生成树）：

Kruskal重构树是一个二叉树；

废话。

Kruskal重构树的叶子没有点权，其他点都有点权；

废话。

Kruskal重构树是完全二叉树（除叶结点外，每个结点都有两个儿子）；

废话。

原图中的两点$u$、$v$在Kruskal重构树上的LCA的点权是原图中$u$到$v$的所有路径中最大边的最小值。

先考虑：由于是按边权从小到大插入的，所以某个非根非叶子结点的点权一定比它的父亲的点权小； 所以，$u$和$v$在Kruskal重构树上的LCA的点权，就是在最小生成树上的$u\to v$的路径（由于是树，所以是唯一路径）中的最长边； 又因为是最小生成树，所以满足这个最长边最小。

例题

两道板子题

A NOIP2013货车运输 B BZOJ3732 Network 这两道题利用上面的最后一个性质，输出LCA的点权即可。

当然，这两道题也可以直接用最小（最大）生成树来做，用一个倍增数组记录路径上边权的最大值（最小值）就行了。

下面是A题的两种方法的代码：

Kruskal重构树（这道题可能不连通= =，详见下面注释的部分） #include<bits/stdc++.h> using namespace std; int read(){ int x=0;bool f=0;char c=getchar(); while(c<'0'||c>'9') f|=c=='-',c=getchar(); while(c>='0'&&c<='9') x=x*10+(c^48),c=getchar(); return f?-x:x; } #define LOG 15 #define MAXN 10000 #define MAXM 50000 struct KruskalTree{ #define MAXP (MAXN*2) struct Edge{ int u,v,w; }; int fa[MAXP+5]; int Find(int x){ return fa[x]==x?x:fa[x]=Find(fa[x]); } int W[MAXP+5]; bool vis[MAXP+5]; vector<int> G[MAXP+5]; int Anc[MAXP+5][LOG+5],Dep[MAXP+5]; void dfs(int u,int fa,int dep){ Dep[u]=dep,vis[u]=1; for(int v:G[u]){ if(v!=fa){ Anc[v][0]=u; dfs(v,u,dep+1); } } } void Init(int N){ for(int i=1;i<=N;i++) if(!vis[i]) dfs(Find(i),-1,0); //下面的注释掉的写法会T // for(int i=1;i<=N;i++) // if(!Anc[i][0]){ // Anc[i][0]=i; // dfs(i,-1,1); // } for(int j=1;j<=LOG;j++) for(int i=1;i<=N;i++) Anc[i][j]=Anc[Anc[i][j-1]][j-1]; } void Build(Edge *E,int N,int M){ sort(E+1,E+M+1,[=](Edge i,Edge j){ return i.w>j.w; }); int cnt=N; for(int i=1;i<=2*N;i++) fa[i]=i; for(int i=1;i<=M;i++){ int u=E[i].u,v=E[i].v; int x=Find(u),y=Find(v); if(x!=y){ W[++cnt]=E[i].w; G[cnt].push_back(x); G[cnt].push_back(y); fa[x]=fa[y]=cnt; } } Init(2*N); } int Query(int u,int v){ if(Find(u)!=Find(v)) return -1; if(Dep[u]<Dep[v]) swap(u,v); int k=Dep[u]-Dep[v]; for(int i=LOG;i>=0;i--) if(k&(1<<i)) u=Anc[u][i]; if(u==v) return u; for(int i=LOG;i>=0;i--) if(Anc[u][i]!=Anc[v][i]) u=Anc[u][i],v=Anc[v][i]; return W[Anc[u][0]]; } }; int N,M,Q; KruskalTree T; KruskalTree::Edge E[MAXM+5]; int main(){ N=read(),M=read(); for(int i=1;i<=M;i++) E[i].u=read(),E[i].v=read(),E[i].w=read(); T.Build(E,N,M); Q=read(); while(Q--){ int u=read(),v=read(); printf("%d\n",T.Query(u,v)); } return 0; } 直接最小生成树+倍增： #include<cstdio> #include<vector> #include<cstring> #include<algorithm> using namespace std; #define MAXN 10000 #define MAXM 50000 #define INF 0x3f3f3f3f #define PII pair<int,int> struct Edge{ int u,v,w; }E[MAXM+5]; bool cmp(Edge x,Edge y){ return x.w>y.w; } int N,M; vector<PII> G[MAXN+5]; int fa[MAXN+5]; int Find(int x){return fa[x]?fa[x]=Find(fa[x]):x;} bool Same(int x,int y){return Find(x)==Find(y);} void Unite(int x,int y){fa[Find(x)]=Find(y);} void Kruskal(){ sort(E+1,E+M+1,cmp); for(int i=1;i<=M;i++){ if(Same(E[i].u,E[i].v)) continue; Unite(E[i].u,E[i].v); G[E[i].u].push_back(make_pair(E[i].v,E[i].w)); G[E[i].v].push_back(make_pair(E[i].u,E[i].w)); } } #define LOG 15 int Dep[MAXN+5]; int Anc[MAXN+5][LOG+5]; int MinW[MAXN+5][LOG+5]; void dfs(int u,int fa,int d){ Dep[u]=d; for(int i=0;i<int(G[u].size());i++){ int v=G[u][i].first,w=G[u][i].second; if(v!=fa){ Anc[v][0]=u; MinW[v][0]=w; dfs(v,u,d+1); } } } void Init(){ for(int i=1;i<=N;i++) if(!MinW[i][0]) dfs(i,Anc[i][0]=i,1); for(int j=1;j<=LOG;j++) for(int i=1;i<=N;i++){ Anc[i][j]=Anc[Anc[i][j-1]][j-1]; MinW[i][j]=min(MinW[i][j-1],MinW[Anc[i][j-1]][j-1]); } } int GetAns(int u,int v){ if(Dep[u]<Dep[v]) swap(u,v); int k=Dep[u]-Dep[v],ret=INF; for(int i=LOG;i>=0;i--) if(k&(1<<i)){ ret=min(ret,MinW[u][i]); u=Anc[u][i]; } if(u==v) return ret; for(int i=LOG;i>=0;i--) if(Anc[u][i]!=Anc[v][i]){ ret=min(ret,min(MinW[u][i],MinW[v][i])); u=Anc[u][i],v=Anc[v][i]; } if(Anc[u][0]!=Anc[v][0]) return -1; return min(ret,min(MinW[u][0],MinW[v][0])); } int main(){ scanf("%d%d",&N,&M); for(int i=1;i<=M;i++) scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].w); Kruskal(); Init(); int Q; scanf("%d",&Q); while(Q--){ int u,v; scanf("%d%d",&u,&v); printf("%d\n",GetAns(u,v)); } }

一道令人愉悦的树套树

BZOJ3545 [ONTAK2010]Peaks 这道题有强制在线版：BZOJ3551 [ONTAK2010]Peaks加强版

如果你不想过分地卡常，请在黑暗爆炸OJ上交。

题解：BZOJ 3551 [ONTAK2010]Peaks加强版