最小生成树kruskal算法44pts求调……
查看原帖
最小生成树kruskal算法44pts求调……
551630
Lemon_zqp楼主2024/1/28 15:31
#include<bits/stdc++.h>
using namespace std;

int fa[5005];
double vis[5005];

struct node{
	int from, to, w;
};

vector<node> edge;

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

void com(int a, int b){
	if(find(a) != find(b)){
		fa[a] = b;
	}
}

bool cmp(node x, node y){
	return x.w < y.w;
}

int main()
{
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		fa[i] = i;
	}
	for(int i = 0; i < m; i++){
		int a, b, c;
		cin >> a >> b >> c;
		edge.push_back({a, b, c});
//		com(a, b);
	}
	sort(edge.begin(), edge.end(), cmp);
	int ans = 0, num = 0;
	for(int i = 0; i < m; i++){
		if(find(edge[i].from) != find(edge[i].to)){
			com(edge[i].to, edge[i].from);
			num++;
			ans += edge[i].w;
			if(num == n - 1) break;
//			cout << ans << " " << edge[i].w << endl; 
		}
	}
	if(num != n - 1) cout << "orz";
	else cout << ans;
	return 0;
}

2024/1/28 15:31
加载中...