Author: lllyouo
Date: 20250226
tag: 最小生成树、连通块
link: https://www.luogu.com.cn/problem/P1396

问题描述

link

分析

考虑做最小生成树算法，当节点 $s$ 与 $t$ 连通时结束，输出此时的边权即可。

参考代码

#include <bits/stdc++.h>
using namespace std;

struct Edge {
	int u, v, w;

	bool operator< (const Edge& x) {
		return w < x.w;
	}
};

vector<Edge> e;
int n, m, s, t, p[10010], ans;

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

int main() {
	cin >> n >> m >> s >> t;
	for (int i = 0; i < m; i++) {
		int a, b, c; cin >> a >> b >> c;

		e.push_back({a, b, c});
	}

	for (int i = 1; i <= n; i++) p[i] = i;
	sort(e.begin(), e.end());

	for (auto x : e) {
		int fu = find(x.u);
		int fv = find(x.v);

		if (fu != fv) {
			p[fu] = fv;
			ans = max(ans, x.w);
		}
		if (find(s) == find(t)) {
			cout << ans << endl;
			break;
		}
	}

	return 0;
}