Kruscal(最小生成树)算法模版

简介: 1 const int maxn=400;//最大点数 2 const int maxm=10000;//最大边数 3 int n,m;//n表示点数,m表示边数 4 struct edge{int u,v,w;} e[maxm];//u,v,w分别表示该边的两个顶点和权值 5 bool cmp(edge a,edge b) 6 { 7 return a.
 1 const int maxn=400;//最大点数
 2 const int maxm=10000;//最大边数
 3 int n,m;//n表示点数,m表示边数
 4 struct edge{int u,v,w;} e[maxm];//u,v,w分别表示该边的两个顶点和权值
 5 bool cmp(edge a,edge b)
 6 {
 7     return a.w<b.w;
 8 }
 9 int fa[maxn];//因为需要用到并查集来判断两个顶点是否属于同一个连通块
10 int find(int x)
11 {
12     if(x==fa[x]) return x;
13     else return fa[x]=find(fa[x]);
14 }
15 int kruscal()
16 {
17     int ans=-1;
18     sort(e+1,e+1+m,cmp);
19     for(int i=1;i<=n;++i) fa[i]=i;//初始化并查集
20     int cnt=n;
21     for(int i=1;i<=m;++i)
22     {
23         int t1=find(e[i].u);
24         int t2=find(e[i].v);
25         if(t1!=t2)
26         {
27             if(cnt==1) break;
28             fa[t1]=t2;
29             ans=max(ans,e[i].w);
30             cnt--;
31         }
32     }
33     return ans;
34 }

 

目录
相关文章
|
11天前
|
算法 测试技术 C++
【广度优先搜索】【拓扑排序】【C++算法】913. 猫和老鼠
【广度优先搜索】【拓扑排序】【C++算法】913. 猫和老鼠
|
5月前
|
算法 搜索推荐
Kruskal算法
Kruskal算法
|
8月前
|
算法 测试技术
畅通工程 (最小生成树)
畅通工程 (最小生成树)
34 0
|
8月前
|
算法
dijkstra最短路算法
dijkstra最短路算法
|
11月前
|
机器学习/深度学习 算法
最短路算法
最短路算法
42 0
kruskal算法的实现
kruskal算法的实现
|
算法
Kruskal算法(克鲁斯卡尔)最小生成树
Kruskal算法(克鲁斯卡尔)最小生成树
109 0
|
存储 算法 C语言
数据结构题:克鲁斯卡尔(Kruscal)算法求最小生成树
数据结构题:克鲁斯卡尔(Kruscal)算法求最小生成树
数据结构题:克鲁斯卡尔(Kruscal)算法求最小生成树
2021杭电多校第三场-Road Discount-wqs二分+最小生成树
get函数是求出将黑色的边权加上一个值x之后的一个花费,我们会这个函数处理出x=-1000->1000的所有情况,然后将信息储存在save中,然后在询问的时候,直接遍历save集合,遇见满足情况的便直接输出,否则输出-1,虽然没有-1的情况/doge
124 0
2021杭电多校第三场-Road Discount-wqs二分+最小生成树
|
算法 C++
算法模版:暴力搜索之BFS
算法模版:暴力搜索之BFS
算法模版:暴力搜索之BFS