最小生成树

发布时间:2022-06-29 发布网站:脚本宝典
脚本宝典收集整理的这篇文章主要介绍了最小生成树脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。

根据贪心,在建树时优先选择长度小的边

通过并查集判断两个点是否已联通,如果已联通,则跳过,如果为联通,则连接  (因为是树,所以仅有一条路径)

P3366 【模板】最小生成树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=5005,M=200005;
 4 int n,m,ans;
 5 int f[N];
 6 struct node
 7 {
 8     int from,to,le;
 9 };
10 node e[M];
11 int cmp(node x,node y)
12 {
13     return x.le<y.le;
14 }
15 int find(int x)
16 {
17     if(x==f[x])return x;
18     else return f[x]=find(f[x]);
19 }
20 int main()
21 {
22     cin>>n>>m;
23     for(int i=1;i<=n;++i)f[i]=i;
24     for(int i=1;i<=m;++i)
25     {
26         cin>>e[i].from>>e[i].to>>e[i].le;
27     }
28     sort(e+1,e+m+1,cmp);
29     for(int i=1;i<=m;++i)
30     {
31         int fro=e[i].from,t=e[i].to;
32         if(find(fro)!=find(t))
33         {
34             ans+=e[i].le;
35             f[find(fro)]=f[find(t)];
36         }
37     }
38     int fa=find(e[1].from);
39     for(int i=1;i<=n;++i)
40     {
41         if(fa!=find(i))
42         {
43             cout<<"orz";
44             return 0;
45         }
46     }
47     cout<<ans;
48     return 0;
49 }

 

脚本宝典总结

以上是脚本宝典为你收集整理的最小生成树全部内容,希望文章能够帮你解决最小生成树所遇到的问题。

如果觉得脚本宝典网站内容还不错,欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。
标签: