KRUSKAL 79pts求助
查看原帖
KRUSKAL 79pts求助
1048358
zhiyinnitaimeiohbaby楼主2024/12/28 10:11
#include <bits/stdc++.h>
using namespace std;
int n,m;
struct edge{
	int u,v,l;
};
edge e[114514];
int id[114514];
string s[114514];
bool cmp(edge a,edge b){
	return (a.l < b.l);
}
int root(int u){
	return id[u]==u?u:id[u]=root(id[u]);
}
void Kruskal(){
	sort(e+1,e+1+m,cmp);
	int cnt = 0,ans = 0;;
	for(int i = 1;i <= n;i++) id[i] = i;
	for(int i = 1;i <= m;i++){
		int u = root(e[i].u);
		int v = root(e[i].v);
		if(u==v) continue;
		id[u] = v;
		cnt++;
		ans+=e[i].l;
		if(cnt == n-1) break;
	}
	if(cnt == n-1) cout<<ans;
	else cout<<"orz";
	return ;
}
int main(){
	cin>>n>>m;
	for(int i = 1;i <= m;i++){
		int u,v,l;cin>>u>>v>>l;
		e[i] = {u,v,l};
	}
	Kruskal();
	return 0;
	}

2024/12/28 10:11
加载中...