最小生成树10分
查看原帖
最小生成树10分
289296
zymooll楼主2021/11/13 11:31

-Wall编译无错误 代码见下:

#include<bits/stdc++.h>
using namespace std;
int n, m, ans;
int fa[310];
int find(int x) {
	if (x != fa[x])fa[x] = find(fa[x]);
	return fa[x];
}
void marge(int x, int y) {
	fa[find(x)] = find(y);
}
bool check(int x, int y) {
	return find(x) == find(y);
}
struct Edge {
	int u, v, w;
	bool operator<(const Edge& x1) {
		return w < x1.w;
	}
};
vector<Edge>edge;
int main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		Edge ls;
		cin >> ls.u >> ls.v >> ls.w;
		edge.push_back(ls);
	}
	sort(edge.begin(), edge.end());
	for (int i = 0, js = 0; i < m && js != n - 1; i++) {
		int u = edge[i].u, v = edge[i].v, w = edge[i].w;
		if (!check(u, v))continue;
		marge(u, v);
		ans = w;
		js++;
	}
	cout << n - 1 << " " << ans;
	return 0;
}
2021/11/13 11:31
加载中...