AcWing 859 Kruskal算法求最小生成树
发布日期:2021-05-28 16:26:41 浏览次数:10 分类:技术文章

本文共 1589 字,大约阅读时间需要 5 分钟。

题目描述:

给定一个n个点m条边的无向图,图中可能存在重边和自环,边权可能为负数。

求最小生成树的树边权重之和,如果最小生成树不存在则输出impossible。

给定一张边带权的无向图G=(V, E),其中V表示图中点的集合,E表示图中边的集合,n=|V|,m=|E|。

由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树,其中边的权值之和最小的生成树被称为无向图G的最小生成树。

输入格式

第一行包含两个整数n和m。

接下来m行,每行包含三个整数u,v,w,表示点u和点v之间存在一条权值为w的边。

输出格式

共一行,若存在最小生成树,则输出一个整数,表示最小生成树的树边权重之和,如果最小生成树不存在则输出impossible。

数据范围

1≤n≤10^5,

1≤m≤2∗10^5,
图中涉及边的边权的绝对值均不超过1000。

输入样例:

4 51 2 11 3 21 4 32 3 23 4 4

输出样例:

6

分析:

kruskal算法的时间复杂度为O(mlogm),用于求解稀疏图的最小生成树问题,而prim算法用于解决稠密图的最小生成树问题。kruskal算法是基于贪心思想的,每次选取权重最小的边加入最小生成树,并且需要保证新加入的边不会构成环。

kruskal算法一般使用并查集实现,具体算法的流程就是先对各个边按边权从小到大排序,按照边权从小到大选取边加入最小生成树的集合,判断新加入的边是否会构成环,只需要判断下边的两个顶点是否在同一集合中即可,在则说明边的两个顶点均已加入并查集中,不可再添加边了。

#include 
#include
using namespace std;const int maxn = 200005,INF = 0x3f3f3f3f;int n,m;int fa[100005];struct Edge{ int x,y,w; bool operator < (const Edge &e)const{ return w < e.w; }}edge[maxn];int get(int x){ if(x != fa[x]) return fa[x] = get(fa[x]); return fa[x];}int kruskal(){ sort(edge,edge + m); for(int i = 1;i <= n;i++) fa[i] = i; int res = 0,cnt = 0; for(int i = 0;i < m;i++){ int w = edge[i].w,x = edge[i].x,y = edge[i].y; int u = get(x),v = get(y); if(u != v){ fa[u] = v; res += w; cnt++; } } if(cnt < n - 1) return INF; return res;}int main(){ scanf("%d%d",&n,&m); int u,v,w; for(int i = 0;i < m;i++){ scanf("%d%d%d",&u,&v,&w); edge[i] = {u,v,w}; } int res = kruskal(); if(res == INF) puts("impossible"); else printf("%d\n",res); return 0;}

 

转载地址:https://blog.csdn.net/qq_30277239/article/details/101066119 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:AcWing 860 染色法判定二分图
下一篇:AcWing 858 Prim算法求最小生成树

发表评论

最新留言

感谢大佬
[***.8.128.20]2024年02月02日 03时53分16秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章