两点间最优通信稳定性等于所有路径中最小边权的最大值，这正是最大生成森林上的路径最小边权；先 Kruskal 建最大生成森林，再用倍增 LCA 查询路径最小边。
OJ: luogu
题目 ID: P9235
难度:提高+/省选-
标签:图论并查集LCA最长生成树
日期: 2026-06-20 02:48
题意
给一张无向带权图。
一条路径的稳定性定义为：
- 这条路径上所有边权的最小值
两点 A, B 之间的通信稳定性定义为：
- 所有
路径里，稳定性最大的那一条
也就是典型的：
- 最大化路径最小边权
如果两点根本不连通，输出 -1。
样例图
样例图如下：
graph G {
1 -- 2 [label="5"];
2 -- 3 [label="6"];
3 -- 4 [label="1"];
1 -- 4 [label="3"];
5;
}
例如
- 路径
2-3-4的稳定性是 - 路径
2-1-4的稳定性是
所以最优答案是 3。
思路
先看一个最直接的小数据暴力：
cpp
// brute.cpp：直接做 maximin Floyd。
// dist[i][j] 表示 i 到 j 的所有路径里，“最小边权”的最大值。
// 复杂度高，只适合小数据对拍。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 25;
int n, m, q;
int dist_arr[MAXN][MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> q;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist_arr[i][j] = 0;
}
dist_arr[i][i] = 1000000000;
}
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
dist_arr[u][v] = max(dist_arr[u][v], w);
dist_arr[v][u] = max(dist_arr[v][u], w);
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist_arr[i][j] = max(dist_arr[i][j], min(dist_arr[i][k], dist_arr[k][j]));
}
}
}
while (q--) {
int x, y;
cin >> x >> y;
if (dist_arr[x][y] == 0) {
cout << -1 << '\n';
} else {
cout << dist_arr[x][y] << '\n';
}
}
return 0;
}brute.cpp 用的是经典的 maximin Floyd：
表示 到 的最大瓶颈值 - 转移是
这个思路完全正确，但 n 到 1e5 时显然不可能跑 Floyd。
关键观察是：
- 这题问的“最大化路径最小边权”，等价于最大生成树上的路径最小边权
原因和最小生成树里常见的瓶颈路性质一样，只不过这里用的是：
- 最大生成森林
具体地说：
- 按边权从大到小做 Kruskal
- 得到一片最大生成森林
- 如果两点不在同一棵树里，答案就是
-1 - 如果在同一棵树里，答案等于它们在这棵树上唯一路径的最小边权
所以整题的难点只剩下：
- 如何快速求树上两点路径最小边权
这就是标准的倍增 LCA 扩展。
除了祖先表 up[u][j] 之外，再维护：
：从 往上跳 层，这段路径上的最小边权
查询时：
- 先把深的点提到同一层，并更新答案最小值
- 再让两个点一起往上跳
- 最后把到 LCA 下面那两条边也算进去
这样每次查询就是
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 5;
const int MAXM = 300000 + 5;
const int MAXE = 2 * MAXN + 5;
const int LOG = 18;
const int INF = 0x3f3f3f3f;
struct Edge {
int u, v, w;
bool operator<(const Edge &other) const {
return w > other.w;
}
} edges[MAXM];
int n, m, q;
// 最大生成森林
int head[MAXN], to[MAXE], nxt[MAXE], wgt[MAXE], edge_cnt;
// 并查集
int fa[MAXN], siz[MAXN];
// 倍增 LCA
int depth_arr[MAXN];
int up[MAXN][LOG];
int min_edge[MAXN][LOG]; // 跳 2^j 层时路径上的最小边权
bool vis[MAXN];
void init_graph(int n) {
edge_cnt = 0;
for (int i = 1; i <= n; i++) {
head[i] = 0;
depth_arr[i] = 0;
vis[i] = false;
for (int j = 0; j < LOG; j++) {
up[i][j] = 0;
min_edge[i][j] = INF;
}
}
}
void add_edge(int u, int v, int w) {
edge_cnt++;
to[edge_cnt] = v;
nxt[edge_cnt] = head[u];
wgt[edge_cnt] = w;
head[u] = edge_cnt;
}
int find_root(int x) {
if (fa[x] == x) {
return x;
}
fa[x] = find_root(fa[x]);
return fa[x];
}
bool unite(int x, int y) {
x = find_root(x);
y = find_root(y);
if (x == y) {
return false;
}
if (siz[x] < siz[y]) {
swap(x, y);
}
fa[y] = x;
siz[x] += siz[y];
return true;
}
void build_forest() {
for (int i = 1; i <= n; i++) {
fa[i] = i;
siz[i] = 1;
}
sort(edges + 1, edges + m + 1);
for (int i = 1; i <= m; i++) {
int u = edges[i].u;
int v = edges[i].v;
int w = edges[i].w;
if (unite(u, v)) {
add_edge(u, v, w);
add_edge(v, u, w);
}
}
}
void build_lca() {
vector<int> st;
for (int root = 1; root <= n; root++) {
if (vis[root]) {
continue;
}
vis[root] = true;
depth_arr[root] = 0;
up[root][0] = 0;
min_edge[root][0] = INF;
st.push_back(root);
while (!st.empty()) {
int u = st.back();
st.pop_back();
for (int i = head[u]; i != 0; i = nxt[i]) {
int v = to[i];
if (v == up[u][0]) {
continue;
}
vis[v] = true;
depth_arr[v] = depth_arr[u] + 1;
up[v][0] = u;
min_edge[v][0] = wgt[i];
for (int j = 1; j < LOG; j++) {
up[v][j] = up[up[v][j - 1]][j - 1];
min_edge[v][j] = min(min_edge[v][j - 1], min_edge[up[v][j - 1]][j - 1]);
}
st.push_back(v);
}
}
}
}
int query(int x, int y) {
if (find_root(x) != find_root(y)) {
return -1;
}
int ans = INF;
if (depth_arr[x] < depth_arr[y]) {
swap(x, y);
}
int diff = depth_arr[x] - depth_arr[y];
for (int j = 0; j < LOG; j++) {
if (diff & (1 << j)) {
ans = min(ans, min_edge[x][j]);
x = up[x][j];
}
}
if (x == y) {
return ans;
}
for (int j = LOG - 1; j >= 0; j--) {
if (up[x][j] != up[y][j]) {
ans = min(ans, min_edge[x][j]);
ans = min(ans, min_edge[y][j]);
x = up[x][j];
y = up[y][j];
}
}
ans = min(ans, min_edge[x][0]);
ans = min(ans, min_edge[y][0]);
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> q;
init_graph(n);
for (int i = 1; i <= m; i++) {
cin >> edges[i].u >> edges[i].v >> edges[i].w;
}
build_forest();
build_lca();
while (q--) {
int x, y;
cin >> x >> y;
cout << query(x, y) << '\n';
}
return 0;
}复杂度
预处理：
- Kruskal 建最大生成森林：
- 倍增预处理：
每次查询：
空间复杂度：
总结
这题的核心不是最短路，而是瓶颈路。
真正要记住的一句话是：
- 两点间“最大化路径最小边权”的答案，可以放到最大生成森林上去查
于是整题自然分成两层：
- 并查集 + Kruskal 建最大生成森林
- 倍增 LCA 查询树上路径最小边权
本质上是一道非常标准的：
最大生成树性质 + LCA
组合题。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
