洛谷 P9235 分析（别看）

科技起源的小号1

2026-08-23 12:35:50

发布于：天津

3阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个具体值

1.2 题目背景、允许、禁止与限制

背景：
有一张图， $n$ 个设备和 $m$ 条物理连接，第 $i$ 条物理连接有一个权值 $w_i$
允许：
对于从设备 $A$ 到设备 $B$ 的一条经过了若干个物理连接的路径，我们记这条路径的稳定性为其经过所有连接中稳定性最低的那个
我们记设备 $A$ 到设备 $B$ 之间通信的稳定性为 $A$ 至 $B$ 的所有可行路径的稳定性中最高的那一条
求任意两点之间的通信稳定性（若不存在道路，则输出 $-1$ ）

1.3 题目数据范围与猜测

$O(n~log~m)$

1.4 一句话概括题意

有一张无向带权图
求任意两点所有路径经过边中最小值最大是多少

2 题目破题推导

2.1 第一步：正向思维转逆向思维

我们考虑将“最小值最大”转化，变为一张图的最大生成树上两点之间最小的那条边

2.2 第二步：证明

命题：一张图上的节点 $A$ 到 $B$ 之间所有路径经过边中最小值的所有可能中的最大值 $=$ 一张图的最大生成树中 $A$
设无向图 $G=(V,E)$ ，每条边 $e\in E$ 拥有边权 $w(e)$ 。
对图中任意两点 $A,B$ ，定义

$f(A,B)=\max_{\substack{P\text{ 是}G\text{中}A\to B\text{的路径}}} \Big\{\;\min_{e\in P} w(e)\;\Big\}$

$f(A,B)$ 的含义：枚举 $A$ 到 $B$ 的全部路径，每条路径取路径上边权的最小值，再对这些最小值取最大值。

设 $T$ 是图 $G$ 的一棵最大生成树， $P_T$ 代表树 $T$ 上 $A$ 到 $B$ 的唯一路径。记

$val_T=\min_{e\in P_T} w(e)$

求证：

$\boldsymbol{f(A,B)=val_T}$

证明：

第一步：证明 $f(A,B)\ge val_T$

最大生成树 $T$ 的所有边都来自原图 $G$ ，因此树上路径 $P_T$ 也是原图中一条合法的 $A\to B$ 路径。

根据 $f(A,B)$ 的定义： $f(A,B)$ 是所有合法路径的 $\min\{w(e)\}$ 的最大值。集合的最大值一定大于等于集合中任意一个元素。把路径 $P_T$ 纳入考虑，得到

$f(A,B)\;\ge\; \min_{e\in P_T}w(e) = val_T$

第二步：证明 $f(A,B)\le val_T$ （反证法）

反设 $f(A,B) > val_T$ 。

根据 $f(A,B)$ 的定义，则原图中一定存在某条路径 $P'$ ，满足

$\min_{e\in P'} w(e) = X > val_T$

该式等价于路径 $P'$ 的每一条边权都满足 $w(e)\ge X>val_T$ 。

回顾最大生成树的Kruskal算法：边按权值从大到小排序，依次加入，不构成环则保留。

$val_T$ 是树上 $A,B$ 路径的最小边权，也就是树上 $A,B$ 正是依靠这条权为 $val_T$ 的边才完成连通。
但路径 $P'$ 的全部边权都严格大于 $val_T$ ，说明在Kruskal处理完所有权大于 $val_T$ 的边时， $A$ 与 $B$ 就已经连通。

此时权值为 $val_T$ 的边不再起到连通两个连通块的作用，按照Kruskal规则，这条边不会被选入最大生成树。
这与“权值为 $val_T$ 的边属于最大生成树 $T$ 的 $A-B$ 路径”矛盾。

故假设不成立，因此

$f(A,B)\le val_T$

合并不等式
联立

$\begin{cases} f(A,B)\ge val_T\\ f(A,B)\le val_T \end{cases}$

得到

$\boldsymbol{f(A,B)=val_T}$

3 模型匹配

最大生成树用最小生成树模板改一下（排序改为降序）
树上 $A$ 到 $B$ 的最小值用LCA。但是我们发现题目中并没有提到“图一定连通”，说明可能会有森林，但是依旧在原数组上做LCA即可

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, m, q;
const int N = 1e5 + 10, M = 22;
int fa[N];
void init(){
    for (int i = 1;i <= n;i++){
        fa[i] = i;
    }
}
int get(int x){
    if (fa[x] != x){
        fa[x] = get(fa[x]);
    }
    return fa[x];
}
struct edge{
    int from, to;
    int w;
};
vector<edge> e;
bool cmp(edge x, edge y){
    return x.w > y.w;
}
struct tree_edge{
    int to;
    int w;
};
vector<tree_edge> tree[N];
int f[N][M], mn[N][M];
int dep[N];
void dfs(int u, int fa){
    dep[u] = dep[fa] + 1;
    f[u][0] = fa;
    for (tree_edge v : tree[u]){
        if (v.to == fa) continue;
        mn[v.to][0] = v.w;
        dfs(v.to, u);
    }
}
void init_f_mn(){
    for (int j = 1;j <= 20;j++){
        for (int i = 1;i <= n;i++){
            f[i][j] = f[f[i][j - 1]][j - 1];
            mn[i][j] = min(mn[i][j - 1], mn[f[i][j - 1]][j - 1]);
        }
    }
}
int lca(int u, int v){
    if (dep[u] < dep[v]){
        swap(u, v);
    }
    int ans = LLONG_MAX;
    for (int j = 20;j >= 0;j--){
        if (dep[f[u][j]] >= dep[v]){
            ans = min(ans, mn[u][j]);
            u = f[u][j];
        }
    }
    if (u == v){
        return ans;
    }
    for (int j = 20;j >= 0;j--){
        if (f[u][j] != f[v][j]){
            ans = min(ans, mn[u][j]);
            ans = min(ans, mn[v][j]);
            u = f[u][j];
            v = f[v][j];
        }
    }
    ans = min(ans, mn[u][0]);
    ans = min(ans, mn[v][0]);
    return ans;
}

signed main(){

    cin >> n >> m >> q;
    for (int i = 1;i <= m;i++){
        int u, v, w;
        cin >> u >> v >> w;
        e.push_back({u, v, w});
        e.push_back({v, u, w});
    }
    init();
    sort(e.begin(), e.end(), cmp);
    int cnt = 0;
    for (edge now : e){
        int u = now.from, v = now.to;
        int w = now.w;
        int ru = get(u), rv = get(v);
        if (ru != rv){
            cnt++;
            fa[ru] = rv;
            tree[u].push_back({v, w});
            tree[v].push_back({u, w});
        }
        if (cnt == n - 1){
            break;
        }
    }
    for (int i = 1;i <= n;i++){
        if (fa[i] == i){
            dfs(i, 0);// lca应该是0，-1会越界
        }
    }
    init_f_mn();
    while(q--){
        int xi, yi;
        cin >> xi >> yi;
        if (get(xi) != get(yi)){
            cout << -1 << endl;
            continue;
        }
        cout << lca(xi, yi) << endl;
    }
    
    return 0;
}