AC

lzhh_lzhh26  •  1个月前


/*
2.另一种算法
  1.对所有边按边的权值排序
  2.依次从小到大考虑某条边是否加入
    2.1怎么判断是多加的(加了之后有没有环)
	   即判断两个点是否已经加入了同一个连通分量
	   即使用并查集
    2.2如果在同一个连通分量,则跳过
	2.3如果不在同一个连通分量,则合并 
*/ 

#include<iostream>
#include<algorithm> 
using namespace std;
struct edge{
	int a,b;
	int len;
	bool operator < (edge e2){
		return len<e2.len;
	}
}list[2000005]; 
int n,m;
int group[100005];		//连通分量看作一组组 group[i]的值表示编号为i的节点属于那个连通分量 
int find(int x){	//并查集 查连通分量编号 
	if(x!=group[x]){
		group[x]=find(group[x]);
	}
	return group[x];
} 
int main(){
	cin>>n>>m;		//n点m边 
	for(int i=0;i<m;i++){
		cin>>list[i].a>>list[i].b>>list[i].len;
	} 
	for(int i=1;i<=n;i++){
		group[i]=i;		//连通分量初始编号是它自己 
	}
	long long ans=0;
	sort(list,list+m);		//数组按边从小到大排序 
	for(int i=0;i<m;i++){		//从小到大依次考虑某条边加入 
		if(find(list[i].a)!=find(list[i].b)){		//边的两点不在同一个连通分量 
			ans+=list[i].len;		//记录答案
			group[find(list[i].a)]=find(list[i].b);		//合并连通分量 
		}
	} 
	//接下来查图是否连通:即看并查集是否全部是一个组 
	int gl=find(1);
	for(int i=2;i<=n;i++){
		//检查所有点是否是和1是同一个连通分量 
		if(gl!=find(i)){
			cout<<"orz"<<endl;
			return 0;
		}
	} 
	cout<<ans<<endl; 
	return 0;
}

评论:

请先登录,才能进行评论