P1396

营救

题目背景

“咚咚咚……”“查水表！”原来是查水表来了，现在哪里找这么热心上门的查表员啊！小明感动得热泪盈眶，开起了门……

题目描述

妈妈下班回家，街坊邻居说小明被一群陌生人强行押上了警车！妈妈丰富的经验告诉她小明被带到了 $t$ 区，而自己在 $s$ 区。

该市有 $m$ 条大道连接 $n$ 个区，一条大道将两个区相连接，每个大道有一个拥挤度。小明的妈妈虽然很着急，但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 $s$ 至 $t$ 的路线，使得经过道路的拥挤度最大值最小。

输入格式

第一行有四个用空格隔开的 $n$ ， $m$ ， $s$ ， $t$ ，其含义见【题目描述】。

接下来 $m$ 行，每行三个整数 $u, v, w$ ，表示有一条大道连接区 $u$ 和区 $v$ ，且拥挤度为 $w$ 。

两个区之间可能存在多条大道。

输出格式

输出一行一个整数，代表最大的拥挤度。

输入输出样例

输入样例 #1

输出样例 #1

说明/提示

数据规模与约定

对于 $30\%$ 的数据，保证 $n\leq 10$ 。
对于 $60\%$ 的数据，保证 $n\leq 100$ 。
对于 $100\%$ 的数据，保证 $1 \leq n\leq 10^4$ ， $1 \leq m \leq 2 \times 10^4$ ， $w \leq 10^4$ ， $1 \leq s, t \leq n$ 。且从 $s$ 出发一定能到达 $t$ 区。

样例输入输出 1 解释

小明的妈妈要从 $1$ 号点去 $3$ 号点，最优路线为 $1 \to 2 \to 3$ 。

题解

1 篇题解

登录后即可使用 Markdown 发布题解。

YuyiLv.6👑 站长管理员

P1396 营救题解 Author: Yuyi 题意分析妈妈在 $s$ 区，小明在 $t$ 区。给出一张无向图（可能有重边），每条边有一个“拥挤度”。我们要求出一条从 $s$ 走到 $t$ 的路径，使得这条路径上拥挤度的最大值尽可能小。这是图论中极其经典的 “瓶颈路径” （Bottleneck Path）问题。其实这个问题跟最小生成树（MST）同宗…

点击展开完整题解点击收起题解

2026年8月9日 22:32

P1396 营救题解

Author: Yuyi

题意分析

妈妈在 $s$ 区，小明在 $t$ 区。给出一张无向图（可能有重边），每条边有一个“拥挤度”。我们要求出一条从 $s$ 走到 $t$ 的路径，使得这条路径上拥挤度的最大值尽可能小。这是图论中极其经典的**“瓶颈路径”**（Bottleneck Path）问题。其实这个问题跟最小生成树（MST）同宗同源，我们完全可以利用 Kruskal 算法 + 并查集 优雅地解决。

正解推导过程

贪心排序：因为我们要让路径上的最大拥挤度尽可能小，那么拥挤度小的道路肯定优先走。所以我们将所有边按拥挤度从小到大排序。
并查集连通：开始遍历排好序的边，利用并查集将边的两个端点连通。只要加入这条边不会形成环（端点不在同一集合），我们就合并它们。
结束判定：在合并的过程中，我们每次都去检查一下起点 $s$ 和终点 $t$ 是否已经在同一个连通块中了（即 find(s) == find(t)）。一旦它们连通，说明我们已经铺通了一条从 $s$ 到 $t$ 的路，由于我们是按从小到大加边的，所以当前加入的这条边的拥挤度，必然就是这条路径上的最大拥挤度，直接输出答案并 break 即可！

正解代码及分析

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dep(i,a,b) for(int i=(a);i>=(b);i--)
#define lowbit(a) (a)&(-a)
using namespace std;
const int maxn = 20005; // 根据最大边数 m<=20000 统一开辟
const int mo = 998244353;
const double pi = acos(-1.0);
template <typename T>
inline void read(T &X)
{
    X = 0;int w = 0; char ch = 0;
    while(!isdigit(ch)) {w |= ch == '-' ;ch = getchar();}
    while(isdigit(ch)) X = X * 10 + (ch^48),ch = getchar();
    if(w) X = -X;
}
int n,m,s,t;
struct Edge
{
    int u,v,w;
}e[maxn];
bool cmp(Edge A,Edge B)
{
    return A.w < B.w;
}
int fa[maxn];
int find(int u)
{
    if(u == fa[u]) return u;
    return fa[u] = find(fa[u]);
}
void solve()
{
    read(n),read(m),read(s),read(t);
    rep(i,1,m) read(e[i].u),read(e[i].v),read(e[i].w);
    if(s == t)
    {
        cout << 0 << endl;
        return;
    }
    rep(i,1,n) fa[i] = i;
    sort(e+1,e+1+m,cmp);
    rep(i,1,m)
    {
        int fu = find(e[i].u);
        int fv = find(e[i].v);
        if(fu != fv)
        {
            fa[fu] = fv;
        }
        if(find(s) == find(t))
        {
            cout << e[i].w << endl;
            break;
        }
    }
    return;
}
int main()
{
    int T=1;
//  freopen("mul.in","r",stdin);
//  freopen("mul.out","w",stdout);
//  read(T);
    while(T--) solve();
    return 0;
}

复杂度分析

时间复杂度：图中有 $M$ 条边，对边进行排序耗时 $O(M \log M)$ 。并查集的单次 find 查询和合并由于路径压缩的存在，时间复杂度极其接近 $O(1)$ ，最多进行 $M$ 次循环判定，所以总时间复杂度为 $O(M \log M)$ ，在 $M \le 20000$ 面前基本可以忽略不计。
空间复杂度：由于将点数数组 fa 和边集数组 e 严格依照 $M \le 20000$ 用常量 maxn = 20005 统一齐平开辟，杜绝直接硬编码数字，空间花费只有几百 KB 左右，空间复杂度 $O(M)$ ，绝对安全通过。

讨论

0 条讨论

登录后即可使用 Markdown 发起讨论和回复。

还没有讨论，来发起第一条吧。

营救