最小生成树(kruskal算法)

其他相关资料:
最小生成树prim算法
并查集+路径压缩
最小生成树模板题
先上原理图:
在这里插入图片描述
原理就是说贪心的从最小边(排个序就好了)找起,如果一条边两个顶点都已被找过(即两个顶点在同一个连通分量),则跳过该边(因为每次找边要确保有新顶点加入连通分量,若该边两个顶点都已被找过则这条边已经没有加入的意义)。但我们又怎么分辨两个顶点是否是来自同一连通分量呢,其实我们可以将一个连通分量看作一个集合,那么就可以用并查集来查询和合并连通分量。
附kruskal代码:

int ly(int a){
if(head[a]==0) return a;
return head[a]=ly(head[a]);
}
void kruskal(){
ans=0;
for(int i=0;i<m;i++){
if(ly(eg[i].u)!=ly(eg[i].v)){//若两顶点来自不同连通分量
ans+=eg[i].w;//加入边权值
vis[eg[i].u]=vis[eg[i].v]=true;//标记找过的顶点
head[ly(eg[i].v)]=ly(eg[i].u);//合并连通分量
}
}
}

附完整代码:

#include //kruskal
using namespace std;
#define int long long
int head[5005]; int n,m; bool vis[5005]; int ans;
struct l{
int u,v,w;
}eg[200005];
bool cmp(l a,l b){
return a.w<b.w;
}
int ly(int a){
if(head[a]==0) return a;
return head[a]=ly(head[a]);
}
void kruskal(){
ans=0;
for(int i=0;i>n>>m;
for(int i=0;i>a>>b>>c;
eg[i].u=a; eg[i].v=b; eg[i].w=c;
}
sort(eg,eg+m,cmp);//先按边权值排序
kruskal();
for(int i=1;i<=n;i++){
if(vis[i]==false){//若没被标记则该图没连通
cout<<"orz"<<endl; return 0;
}
}
cout<<ans<<endl;
}



作者:chineseherofeng

相关推荐

在这里插入图片描述

android#could not resolve all artifacts for configuration ‘:classpath’#

十个必知的排序算法|Python实例系列[1]

自己写mktime、localtime函数

试题 算法提高 题目1 最大最小值