♻️lzhh_lzhh32 • 3个月前
/*
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;
}
评论:
请先登录,才能进行评论