萌新,Kruskal,求助
  • 板块P1396 营救
  • 楼主Ryo_Yamada
  • 当前回复7
  • 已保存回复7
  • 发布时间2020/8/1 12:22
  • 上次更新2023/11/6 21:36:16
查看原帖
萌新,Kruskal,求助
242543
Ryo_Yamada楼主2020/8/1 12:22

rt,Kruskal WA10,求助
我太菜了w /kk

#include <bits/stdc++.h>

using namespace std;

const int maxn = 50005;
struct Node {
	int u, v, w;
	bool operator < (const Node &oth) const {
		return w < oth.w;
	}
} g[maxn];
int fa[maxn];

void init() {
	for(int i = 1; i <= maxn; i++) fa[i] = i;
}

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

void merge(int x, int y) {
	fa[x] = y;
}

int main() {
	init();
 	int n, m, s, t;
    cin >> n >> m >> s >> t;
    for(int i = 1; i <= m; i++) scanf("%d%d%d", &g[i].u, &g[i].v, &g[i].w);
	sort(g + 1, g + n + 1);
	for(int i = 1; i <= m; i++) {
		int x = find(g[i].u), y = find(g[i].v);
		if(x != y) {
			merge(x, y);
			if(find(s) == find(t)) {
				cout << g[i].w << endl;
				return 0;
			}
		}
	}
    return 0;
}
2020/8/1 12:22
加载中...