最小生成树主要应用:
举个例子,两个城市需要光缆联通,且两个城市安装光缆有一定价格,任意两个城市必须联通,求最小价格
这时候就需要运用到最小生成树,当然这个题只是需要套模板,有些变种:https://www.luogu.com.cn/problem/P1195 这道题也是最小生成树,换汤不换药
最小生成树有2种算法:prim和Kruskal
Kruskal:
这个相对比较容易理解,就是将所有边取出来放入一个列表,并且放入时要排序从小到大(用贪心的思想优先选取权值较小的边)。在这之后,就往图中填边。在填边的过程中注意,如果他构成了一个环,舍弃这条边(用并查集来判断是否存在环)(因为如果构成环肯定已经联通,再加入就是多余的),否则就计数器++(计数器是记录填入边的数量),如果到n-1就终止循环,过程中再ans(=0)再加上填入边的权值就可以了QAQ
上图为Kruskal的图,将左边列表依次加入就行了!
#include<bits/stdc++.h> //万能头 using namespace std; int n , m ,fa[50005],cnt,ans,flag;//n个点,m条边,并查集判断环 ,cnt为加入边数 struct node{ int u,v,w; }edge[200005];//意义不明的存边 bool cmp(node a,node b) { return a.w < b.w; }//排序依据,从小到大 int find(int x) { if(fa[x] == x) return x; else return fa[x] = find(fa[x]);//递归+状态压缩 实现并查集的‘查’ } void merg(int a,int b) { int x = find(a),y = find(b); if(x==y) return; else fa[x] = y;//合并函数 } int main() { cin >> n >> m; for(int i = 1 ; i <= n ; i ++) fa[i] = i;//初始化并查集 for(int i = 1 ; i <= m ; i++) cin >>edge[i].u >> edge[i].v >> edge[i].w;//虽然无向图但不影响 sort(edge+1,edge+m+1,cmp); for(int i = 1 ; i <= m ; i++) { int a = edge[i].u,b = edge[i].v,c = edge[i].w; if(cnt == n-1) { break;//如果已经加入了n-1条边,直接跳出 } if(find(a)==find(b)) continue;//如果已经联通跳出进行下一次; ans += c; cnt++; merg(a,b); } if(cnt!=n-1)//判断是否不连通 cout<<"orz"; else cout<<ans; }
亲自手打代码+详细注释
prim:
所谓prim和最短路的dijkstra非常接近,只是目的不同,首先以0为起点,遍历起点为0的边,如果边的v(初始全部为inf)要小于从起点距离+权值就替换,类似蓝白点,标记0,再选一个最小的作为起点
1.更新(以起点为出发点,更新所连接点的距离(初始为正无穷inf))
2.扫描(扫描距离最小的点并且未被标记,将其作为下一次的起点)
3.创建(以扫描到的起点为出发点,重复上述操作,直到覆盖完全部的点)
如果还是看不懂推荐去看这个视频:https://www.bilibili.com/video/BV1Eb41177d1?spm_id_from=333.337.search-card.all.click&vd_source=5f02dc5b35066015d1aef125eacf7273
接下来代码贴上:
#include <bits/stdc++.h>//万能头 #define inf 0x3f3f3f using namespace std; int n,m,cnt,ans,dis[400005],vit[400005],now = 1,tot,minn,head[400005],flag; struct edge{ int v,w,nxt; }e[400005]; void add(int u,int v,int w) { e[++cnt].v = v; e[cnt].w = w; e[cnt].nxt = head[u]; head[u] = cnt; } //链式前向星存图 ,方便后面遍历边 void prim()//噩梦开始的地方 { for(int i = 2 ; i <= n ; i++) dis[i] = inf;//将除了起点之外的点的距离初始化为正无穷 for(int i = head[1];i;i = e[i].nxt) { dis[e[i].v] = min(dis[e[i].v],e[i].w); }//遍历起点1能到达的点 while(++tot<n)//for循环也可以吧 { minn = inf;//找最小值,赋为最大 vit[now] = 1;//将现在的点标记一下,也就是起点 for(int i = 1 ; i <= n ; i ++) { if(!vit[i]&&minn>dis[i]) { minn=dis[i]; now = i; } }//找没被标记的最小值 if(vit[now]) { flag = 1; return; }//如果还是被标记了说明压根没找到,图不连通,返回 ans += minn;//加上到这个点的边的长度 for(int i = head[now];i;i = e[i].nxt) { if(!vit[e[i].v]&&dis[e[i].v]>e[i].w) { dis[e[i].v] = e[i].w; } }//从这个起点更新其他未被标记点 } } int main() { cin >> n >> m;//n个点,m条边 for(int i = 1; i <= m ; i ++) { int x,y,z; cin >> x >> y >> z; add(x,y,z); add(y,x,z); }//无向图,建图 prim(); if(flag) { cout<<"orz"; return 0; }//无联通 printf("%d", ans); return 0; }
prim多用于稠密图,Kruskal多用于稀疏图,比赛时看清数据范围
最后:
标签:cnt,prim,int,最小,生成,edge,起点 From: https://www.cnblogs.com/fk-thank/p/16629061.html