最小生成树_prim算法


P3366 【模板】最小生成树

题目描述

如题,给出一个无向图,求出最小生成树,如果该图不连通,则输出 orz

输入格式

第一行包含两个整数 N,MN,M,表示该图共有 NN 个结点和 MM 条无向边。

接下来 MM 行每行包含三个整数 X_i,Y_i,Z_iXi​,Yi​,Zi​,表示有一条长度为 Z_iZi​ 的无向边连接结点 X_i,Y_iXi​,Yi​。

输出格式

如果该图连通,则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz

输入输出样例

输入 #1

4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出 #1

7

说明/提示

数据规模:

对于 20/%20% 的数据,N/le 5N≤5,M/le 20M≤20。

对于 40/%40% 的数据,N/le 50N≤50,M/le 2500M≤2500。

对于 70/%70% 的数据,N/le 500N≤500,M/le 10^4M≤104。

对于 100/%100% 的数据:1/le N/le 50001≤N≤5000,1/le M/le 2/times 10^51≤M≤2×105,1/le Z_i /le 10^41≤Zi​≤104。

样例解释:

最小生成树_prim算法

所以最小生成树的总边权为 2+2+3=7。

 

 

 

【解析】

本题是一道板子题

首先先看一下prim算法的思路

最小生成树可以看作一个集合

用样例模拟下过程:

minn:每个节点的最小边权

白点:未进入集合的节点

蓝点:已进入集合的节点

红线:最小生成树的边

1.通过输入可以画出下面的图

最小生成树_prim算法

 

2.将图的各个节点赋初值  minn[1]=0,其余赋值为正无穷

3.找到最小边的点1,并加入生成的树(可以理解为一个集合)

最小生成树_prim算法

4.更改与节点1相连的节点边权的最小值

最小生成树_prim算法

5.找到集合外的最小边的节点2,并加入集合

最小生成树_prim算法

6.更改与节点2相连的节点边权的最小值

 

最小生成树_prim算法

7.找到集合外的最小边的节点3,并加入集合

最小生成树_prim算法

8.更改与节点3相连的节点边权的最小值

最小生成树_prim算法

9.找到集合外的最小边的节点4,并加入集合

最小生成树_prim算法

这时候有两种不同的树

最小生成树_prim算法

最小生成树_prim算法

10.更改与节点4相连的节点边权的最小值

最小生成树_prim算法

最小生成树_prim算法

上面的步骤整理一下就变成了:

        for(遍历每个节点){

              找到集合外最小的节点k(与集合有连边)

              更改与k相连的节点的最小值

        }

【代码】

这道题还需要注意判断图是否联通,有的边可能重复输入,要取最小的权值

最小生成树_prim算法

 

 

 

 

 

原创文章,作者:jamestackk,如若转载,请注明出处:https://blog.ytso.com/276463.html

(0)
上一篇 2022年7月23日
下一篇 2022年7月23日

相关推荐

发表回复

登录后才能评论