刚学kruskal求助
查看原帖
刚学kruskal求助
221023
LuomuQDM楼主2020/7/11 22:10

RT 萌新刚学kruskal,结果就在模板题上炸了...

#include<bits/stdc++.h>
using namespace std;
struct node{
	int from;
	int to;
	long long dis;
}edge[200001];
int n,m,l=0;
int fa[5001];
long long ans;
int find(int x){
	return fa[x]=find(fa[x]);
}
bool cmp(node a,node b){
	return a.dis<b.dis;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>edge[i].from>>edge[i].to>>edge[i].dis;
	}
	sort(edge+1,edge+m+1,cmp);
	for(int i=1;i<=n;i++)fa[i]=i;
	while(l<n-1){
		int f=find(edge[l].from),t=find(edge[l].to);
		if(f!=t){
			fa[f]=t;
			ans+=edge[l].dis;
			l++;
		}
	}
	printf("%d\n",ans);
	return 0;
}

全MLE,求助!!!

2020/7/11 22:10
加载中...