【题目来源】
洛谷：P1396 营救 - 洛谷
【题目描述】
妈妈下班回家，街坊邻居说小明被一群陌生人强行押上了警车！妈妈丰富的经验告诉她小明被带到了 \(t\) 区，而自己在 \(s\) 区。
该市有 \(m\) 条大道连接 \(n\) 个区，一条大道将两个区相连接，每个大道有一个拥挤度。小明的妈妈虽然很着急，但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 \(s\) 至 \(t\) 的路线，使得经过道路的拥挤度最大值最小。
【输入】
第一行有四个用空格隔开的 \(n\)，\(m\)，\(s\)，\(t\)，其含义见【题目描述】。
接下来 \(m\) 行，每行三个整数 \(u, v, w\)，表示有一条大道连接区 \(u\) 和区 \(v\)，且拥挤度为 \(w\)。
两个区之间可能存在多条大道。
【输出】
输出一行一个整数，代表最大的拥挤度。
【输入样例】
3 3 1 3
1 2 2
2 3 1
1 3 3
【输出样例】
2
【算法标签】
《洛谷 P1396 营救》 #图论# #二分# #并查集# #最短路# #生成树# #福建省历届夏令营#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 10005; // 最大节点数
const int M = 20005; // 最大边数int n, m, s, t; // n:节点数, m:边数, s:起点, t:终点
int p[N]; // 并查集数组// 边结构体：存储边的两个端点和权重
struct Edge
{int a, b, w; // a:起点, b:终点, w:权重// 重载小于运算符，用于按权重排序bool operator< (const Edge &t) const{return w < t.w;}
} e[M]; // 边数组/*** 并查集查找操作（带路径压缩）* @param x 要查找的节点* @return 节点x的根节点*/
int find(int x)
{if (p[x] != x){p[x] = find(p[x]); // 路径压缩}return p[x];
}int main()
{// 输入节点数、边数、起点、终点cin >> n >> m >> s >> t;// 输入所有边的信息for (int i = 1; i <= m; i++){int u, v, w;cin >> u >> v >> w;e[i] = {u, v, w};}// 将边按权重从小到大排序sort(e + 1, e + m + 1);// 初始化并查集，每个节点独立成集合for (int i = 1; i <= n; i++){p[i] = i;}int ans = -1; // 存储结果：从s到t路径上的最大边权// 使用Kruskal算法思想构建最小生成树for (int i = 1; i <= m; i++){int a = find(e[i].a); // 查找起点所在集合int b = find(e[i].b); // 查找终点所在集合int w = e[i].w; // 当前边的权重// 如果两个端点不在同一个连通分量中if (a != b){p[a] = b; // 合并两个连通分量ans = max(ans, w); // 更新路径上的最大边权// 检查起点和终点是否连通if (find(s) == find(t)){break; // 如果连通，提前退出循环}}}// 输出从s到t路径上的最大边权cout << ans << endl;return 0;
}
【运行结果】
3 3 1 3
1 2 2
2 3 1
1 3 3
2