蓝桥杯之每日一题

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

在这里插入图片描述

解题思路

首先注意到并不是求最短路而是求由s到t之间的路径每条边的权值都为最小那么可以利用最短路的模板来写也可以利用kruskal算法生成最小树。
我使用的是kruskal算法生成最小树的方法。
在kurskal的计算过程中当s和t连通时即可结束进程并输出当前权值此时权值即为路径上的最大权值。

解题代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 10010, M = 2 * N;
//kruskal求最小生成树 
int n,m,s,t,point[N];
class Way{
public:
	int a,b,w;
	bool operator < (const Way &W) const{
		return w < W.w;
	}
} way[M];

int find(int x){
	if(point[x]!=x) point[x] = find(point[x]);
	return point[x];
}

void kruskal(){
	for(int i = 1; i <= n; i++) point[i] = i;//初始化 
	sort(way, way+m);//排序权值最小边
	
	for(int i = 0; i < m; i++){
		int a = way[i].a, b = way[i].b, w = way[i].w;
		a = find(a);
		b = find(b);
		if(a != b) point[a] = b;//合并
		
		if(find(s) == find(t)){//当s和t连通时此时的边即为最大值因为是从大到小排序的 
			cout << w << endl;
			break;
		} 
	}
}

int main(){
	cin >> n >> m >> s >> t;
	for(int i = 0; i < m; i++){
		int a,b,w;
		cin >> a >> b >> w;
		way[i] = {a, b, w};
	}
	kruskal();
	return 0;
}