前置知识
-
最近公共祖先（LCA)
-
\(\text{Kruskal}\) 重构树
简化题意
P9235 网络稳定性
给一个有边权的无向图，给你点 \(u\) 到另一个点 \(v\) 所有的路径上最大的边权最小是多少。
solution
先来介绍一下 \(\text{Kruskal}\) 重构树。这个算法是最小生成树的 \(\text{Kruskal}\) 算法的延申，大体思路是相近的。
构造方法
-
把最小生成树上的边从小到大排序，像最小生成树那样判断连通性即是否加边。
-
假设可以连边，我们就把这条边的边权作为另外两点所在集合根节点的父节点。
-
如果此时遍历完所有的边，即构造完成，得到了重构树。
那么重构树都有些什么优秀的性质呢？
首先一定是一颗二叉树，因为所有的连边过程都是边权节点与两个不相连的根节点相连。其次原图中两个点间所有路径上的边最大权值的最小值一定是构造树上两点的 lca 权值。
那么，对于这一道题，我们该如何去使用？因为这题求的是路径上的最大值的最小值，那么我们就在排序的时候把边按照边权从大到小排序就好了，具体的求 lca 我们使用倍增树剖都是可以的。代码实现的话需要注意构造出来的不一定是一颗树，而很可能是森林，所以需要每一次判断连通性去初始化树剖。
核心部分的代码
void kruskal()
{
sort(e+1,e+m+1,cmp);
for(int i=1;i<=n;++i) f[i]=i;
for(int i=1;i<=m;++i)
{
int u=find(e[i].u),v=find(e[i].v);
if(u==v) continue;
val[++cnt]=e[i].w;
f[cnt]=f[u]=f[v]=cnt;
add(u,cnt),add(v,cnt);
}
for(int i=1;i<=cnt;++i)
{
if(vis[i]) continue; /*这里有效处理森林*/
int rt=find(i);
dfs1(rt),dfs2(rt,rt);
}
}