大佬求助kruskal WA了好几个点。。。
查看原帖
大佬求助kruskal WA了好几个点。。。
90428
胖达和阿极楼主2022/7/26 23:00
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+10;
int n,m,fa[N];
struct edge{
	int u,v,w;
	bool operator <(const edge &a1) const{
		return w<a1.w;
	}
}a[N];
int find(int x){
	return fa[x]==x?fa[x]:fa[x]=find(fa[x]);
}
bool cmp(edge a1,edge a2){
	return a1.w<a2.w;
}
long long kruskal()
{
	long long  cnt = 0,sum =0;
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=m;i++){
		if(find(a[i].u)!=find(a[i].v)){
			fa[a[i].v] = fa[a[i].u];
			sum += a[i].w;
			cnt++;
			if(cnt == n-1){
				return sum;
			}
		}
	}
	return -1;
}
int main(){
	cin>>n>>m;
	int g1,g2,g3;
	for(int i=1;i<=n;i++){
		fa[i] = i;
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&g1,&g2,&g3);
		a[i].u=g1;a[i].w=g3;a[i].v=g2;
		
	}
	int k1 = kruskal();
	if(k1==-1){
		cout<<"orz";
	}else{
		cout<<k1;
	}
	return 0;
}

2022/7/26 23:00
加载中...