蒟蒻求助
查看原帖
蒟蒻求助
638718
xueruo楼主2023/4/1 22:17
#include<iostream>
#include<algorithm> 
#define int long long
using namespace std;
const int N =2e5+10; 
int ge,fa[N],ans,u,v,w,n,m;
struct edge{
	int u,v,w;
}e[N];
int cmp(edge x,edge y){
	return x.w<y.w;
}
int find(int x){
	if(fa[x]==x){
		return x;
	}else{
		return fa[x]=find(fa[x]);
	}
}
bool k(){
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	int cnt=0;
	sort(e+1,e+1+ge,cmp);
	for(int i=2;i<=ge;i++){
		if(find(e[i].u)!=find(e[i].v)){
			cnt++;
			fa[find(e[i].u)]=find(e[i].v);
			ans+=e[i].w;
		}
//		if(cnt==n-1){
//			break;
//		}
	}
	return cnt==n-1;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		e[++ge].u=u;e[ge].v=v;e[ge].w=w;
		e[++ge].v=u;e[ge].u=v;e[ge].w=w;
	}
	if(!k()){ 
		cout<<"orz";
	}else{
		cout<<ans;
	}
	return 0;
}
/*
in
5 6
1 2 1 
1 3 2 
2 4 3 
3 5 4 
3 4 3 
4 5 6
out
11
*/ 

样例没过
我的想法是把最小的那一条边舍去

2023/4/1 22:17
加载中...