【求助】!kruskal算法0分!
查看原帖
【求助】!kruskal算法0分!
372838
pxb0801楼主2022/6/28 21:47
#include<bits/stdc++.h>
using namespace std;
int n,m,fa[305],ans;
struct node{
	int x,y,z;
}a[90005];
bool cmp(node x,node y){
	return x.z<y.z;
}
int find(int x){
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i].x>>a[i].y>>a[i].z;
	}
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=m;i++){
		int fx=find(a[i].x),fy=find(a[i].y);
		if(fx!=fy){
			fa[fy]=fx;
			ans=a[i].z;
		}
	}
	cout<<n-1<<" "<<ans;
	return 0;
}
2022/6/28 21:47
加载中...