最小瓶颈路问题是指在一张无向图中，询问点对$(u,v)$，需要找出从$u$到$v$的一条简单路径，使路径上所有边中最大值最小。
首先我们要知道的一点是：
无向图最小生成树中$u$到$v$的路径一定是$u$到$v$的最小瓶颈路之一（因为最小瓶颈路很可能有多条）
我们知道了这个性质之后，对于多组查询我们有如下思路：
先用$kruskal$算法构建一颗最小生成树$(MST)$，接下来用DFS把最小生成树转化成有根树。然后就变成了对于每个询问$(u,v)$，回答$u$到$v$的路径上的权值最大值。这个可以用倍增$LCA$解决。
具体思路是在$ST$表预处理时，维护一个从该节点到其$k$级父亲中经过的所有边的最大权值。在查询中仍然将$u$和$v$往上跳，同时维护路径中最大值，到其$LCA$结束。（也可以在$DFS$的时候处理，就和倍增$LCA$的两种写法是一样的）
下面看道最LOJ上小瓶颈路的裸题：最小瓶颈路
仔细看代码应该会体会更深：
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10; struct Edge{ int next, to, w; }e[maxn<<1]; struct node{ int u, v, w; }edge[maxn<<1]; bool cmp(node x, node y){ return x.w < y.w; } int n, m, k, cnt; int head[maxn], dep[maxn], f[maxn][20], maxw[maxn][20], fa[maxn]; void add(int u, int v, int w){ e[++cnt].next = head[u]; e[cnt].to = v; e[cnt].w = w; head[u] = cnt; } int find(int x){ return x==fa[x] ? fa[x] : fa[x]=find(fa[x]); } void dfs(int u, int fa) { dep[u] = dep[fa] + 1; for (int i = head[u]; i; i = e[i].next) { int v = e[i].to; if (v==fa) continue; f[v][0] = u, maxw[v][0] = e[i].w; dfs(v, u); } } int query(int x, int y) { if(dep[x]<dep[y]) swap(x, y); int t = (int)(log(dep[x]) / log(2)), res = 0; for (int i = t; i >= 0; i--) { if (dep[f[x][i]] >= dep[y]) { res = max(res, maxw[x][i]); x = f[x][i]; } if (x == y) return res; } for (int i = t; i >= 0; i--) { if (f[x][i] && f[x][i] != f[y][i]) { res = max(res, max(maxw[x][i], maxw[y][i])); x = f[x][i]; y = f[y][i]; } } return max(res, max(maxw[x][0], maxw[y][0])); } int main(){ scanf("%d%d%d", &n, &m, &k); for(int i = 1; i <= n; i++) fa[i] = i; for(int i = 1; i <= m; i++) scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w); //kruskal构建MST sort(edge + 1, edge + 1 + m, cmp); int times = 1; for (int i = 1; i <= m&× <= n-1; i++) { int fx=find(edge[i].u), fy=find(edge[i].v); if(fx!=fy){ fa[fx] = fy, times++; add(edge[i].u, edge[i].v, edge[i].w); add(edge[i].v, edge[i].u, edge[i].w); } } dfs(1, 0); for (int j = 1; (1 << j) <= n; j++){ for (int i = 1; i <= n; i++){ if (f[i][j - 1]){ //孤立点 f[i][j] = f[f[i][j - 1]][j - 1]; maxw[i][j] = max(maxw[i][j - 1], maxw[f[i][j - 1]][j - 1]); } } } while(k--){ int s, t; scanf("%d%d", &s, &t); if (find(s)!=find(t)) puts("-1"); else printf("%d\n", query(s, t)); } return 0; }
参考自：
https://www.cnblogs.com/XSC637/p/7663056.html
https://www.cnblogs.com/xiaoK-778697828/p/9665205.html
https://loj.ac/submission/630088
https://blog.csdn.net/Anxdada/article/details/80420071
https://www.cnblogs.com/konjak/p/6020958.html
原文：https://www.cnblogs.com/wizarderror/p/12179980.html
