解法一:kruskal求最小生成树
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
const int N = 2e6+10;
// 绝绝子思路
// 询问s到t的所有路径中 最大拥挤度最小的是多少
// 用kruskal做 求出最小生成树
// 最小生成树的每一条边都是拥挤度最小的
// 在最小生成树联通的图中 s->t的最大拥挤度必然是最小的
// q1:如何求s->t的最大拥挤度捏?
// 求最小生成树过程中会不会把路径外边给算进去
// a1:使用kruskal算法求最小生成树 这样在求最小生成树的过程中
// 即使st没有联通,有路径外的边参与求最大拥挤度
// 但这些边的权值必然是<=st路径上的最大值的,对答案不影响
// 因为kruskal是按边权排序联通各个点的
// 只要在st联通后 return掉 求出的就是s->t的最大拥挤度的最小值
int n,m,s,t,ans;
int p[N];
struct ss{
int a,b,w;
bool operator <(const ss& x) const{//重载小于号 排序用
return w<x.w;
}
}sc[N];
int find (int x){
if (x!=p[x]) return p[x]=find(p[x]);
return p[x];
}
void kruskal(){//kruskal模板
for (int i=1;i<=n;i++) p[i]=i;
sort(sc+1,sc+1+m);
for (int i=1;i<=m;i++){
int a,b,w;
a=sc[i].a,b=sc[i].b,w=sc[i].w;
a=find(a),b=find(b);
if (a!=b){
p[a]=b;//a->b
ans=max(ans,w);
//即使st没有联通时,有路径外的边参与求最大拥挤度
//但这些边的权值必然是<=st路径上的最大值的,对答案不影响
if (find(s)==find(t)) return ;
//联通后就return掉
}
}
}
int main(){
scanf ("%d%d%d%d",&n,&m,&s,&t);
for (int i=1;i<=m;i++){
int a,b,c;
scanf ("%d%d%d",&a,&b,&c);
sc[i]={a,b,c};
}
kruskal();
cout<<ans;
return 0;
}
解法二:二分+并查集
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
const int N = 2e6+10;
// 求最大值最小 一眼二分
// 对路径的最大值进行二分
// 问题是check函数怎么写
// 可以枚举所有边 联通所有权值<=mid的点
// 最后判断st是否在一个连通块内
// 时间复杂度为m*logw
// m,w<=1e4 安全
int n,m,s,t,ans;
int p[N];
struct ss{
int a,b,w;
bool operator <(const ss& x) const{//重载小于号 排序用
return w<x.w;
}
}sc[N];
int find (int x){
if (x!=p[x]) return p[x]=find(p[x]);
return p[x];
}
bool check(int x){
//遍历所有边 将权值<=x的联通
//最后判断st是否在一个连通块
for (int i=1;i<=n;i++) p[i]=i;
//每轮check都要初始化一遍并查集
for (int i=1;i<=m;i++){
int a,b,w;
a=sc[i].a,b=sc[i].b,w=sc[i].w;
if (w<=x){
a=find(a);
b=find(b);
p[a]=b;//a->b;
if(find(s)==find(t)) return 1;
}
}
return find(s)==find(t);
}
int main(){
scanf ("%d%d%d%d",&n,&m,&s,&t);
for (int i=1;i<=m;i++){
int a,b,c;
scanf ("%d%d%d",&a,&b,&c);
sc[i]={a,b,c};
}
int l,r;
l=1,r=1e4;//题面给出的最大权值
while (l<r){//求路径最大值的最小值
int mid=(l+r)>>1;
if (check(mid)) r=mid;
else l=mid+1;
}
cout<<l;
return 0;
}