kruskal44分求调,WA #3-#10
查看原帖
kruskal44分求调,WA #3-#10
772149
I_love_STL楼主2023/7/16 09:23

RT

#include<bits/stdc++.h>
using namespace std;
int n,m,f[200001];
struct edge{
	int u,v,w;
}k[200001];
bool cmp(edge x,edge y){
	return x.w<y.w;
}
int find(int x){
	if (x==f[x])
		return x;
	return f[x]=find(f[x]);
}
int kruskal(){
	int a=0,s=0;
	for (int i=1;i<=m;++i){
		if (find(f[k[i].u])==find(f[k[i].v]))
			continue;
		a+=k[i].w;
		++s;
		f[k[i].v]=f[k[i].u];
		if (s==n-1)
			return a;
	}
	return 0;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int q;
	cin>>n>>m;
	for (int i=1;i<=n;++i)
		f[i]=i;
	for (int i=1;i<=m;++i)
		cin>>k[i].u>>k[i].v>>k[i].w;
	sort(k+1,k+m+1,cmp);
	q=kruskal();
	if (q)
		cout<<q;
	else
		cout<<"orz";
	return 0;
}
2023/7/16 09:23
加载中...