NC213878. CCA的图
描述
输入描述
第一行四个正整数，n , m , s , t ，分别表示城市数量，道路数量和起点、终点城市编号 。接下来的 m 行，每行三个正整数 u , v , w ，表示有一条连接 u，v 的双向道路，其标记为 w 。
输出描述
一行，两个正整数，表示最大的 L 和 在 L 最大的情况下最小的 R 。
示例1
输入:
4 4 1 4 1 3 3 1 2 2 3 4 2 1 4 1
输出:
2 3
C++(clang++11) 解法, 执行用时: 1414ms, 内存消耗: 38272K, 提交时间: 2020-12-21 19:56:11
#include<bits/stdc++.h>
using namespace std;
struct E{
int a,b,id;
friend bool operator < (E a,E b){
return a.id<b.id;
}
}e[3000005];
int n,m,fa[1000005],s,t;
void init(){
for(int i=1;i<=n;i++)fa[i]=i;
}
int find(int x){
if(fa[x]==x)return x;
return fa[x]=find(fa[x]);
}
void uni(int a,int b){
a=find(a),b=find(b);
fa[a]=b;
}
int main(){
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].id);
int l,r;
sort(e+1,e+m+1);
init();
for(int i=m;i>0;i--){
uni(e[i].a,e[i].b);
if(find(s)==find(t)){
l=i;
break;
}
}
init();
for(int i=l;i<=m;i++){
uni(e[i].a,e[i].b);
if(find(s)==find(t)){
r=i;
break;
}
}
printf("%d %d\n",e[l].id,e[r].id);
return 0;
}