一片黑,MLE
查看原帖
一片黑,MLE
1341247
chenhao_li楼主2024/12/15 14:57

全部MLE,求解

#include<bits/stdc++.h>
using namespace std;

int n,m,k,ans;//k is mst edges,ans
struct edge{
	int u,v,w;
};
edge e[200010];
int fa[5010];
bool cmp(edge a,edge b){
	return a.w>b.w;
}

int Find(int x){
	if(fa[x]==x) return x;
	else return fa[x]=Find(x);
}
void Union(int x,int y){
	int fx=Find(x);
	int fy=Find(y);
	if(fx!=fy) fa[fy]=fx;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) fa[i]=1;//每个顶点自成联通分量
	for(int i=1;i<=m;i++) cin>>e[i].u>>e[i].v>>e[i].w;
	sort(e+1,e+1+m,cmp);
	//kruskal算法
	for(int i=1;i<=m;i++){
		if(Find(e[i].u)!=Find(e[i].v)){//边的两端不是一个联通分量
			k++;
			ans+=e[i].w;
			Union(e[i].u,e[i].v);
			if(k==n-1) break;
		}
	}
	if(k!=n-1) cout<<"orz"<<endl;
	else cout<<ans<<endl;
	return 0;
}
2024/12/15 14:57
加载中...