最小生成树---Kruskal算法
2018-12-04 07:13:52来源:博客园 阅读 ()
~~已会各位大佬们可以跳过QwQ~~,today,we will use a magical algorithm!let is go!
不显摆了(也没得显摆),今天我们用Kruskal算法来解这道题。
1. 定义
int fa[1000100],i,j,k,n,m,s,ans;//基本变量:) struct eige{ int x,y,z; }a[1000100];//主要是为了排序
2. 排序函数定义
int cmp(eige u,eige v){ return u.z<v.z;//将边长从小到大排好;) }
接下来让我们一起来做一件伟大的事情———并查集!(详见博客)
[点这也可以](http://baidu.apphb.com/?q=并查集),
因为如果两个点在不同集合则合并为树,否则跳过。
开始查集
int find(int x){ if(x==fa[x]){//是不是同一个boss return x; } else return fa[x]=find(fa[x]); }
好了,让我们打主程序吧ヾ(??▽?)ノ▄︻┻┳══━一
//输入跳过 sort(a+1,a+1+m,cmp);//排个序 for(i=1;i<=n;i++){ fa[i]=i;//所有人的父节点是自己 } for(i=1;i<=m;i++){ if(find(a[i].x)!=find(a[i].y)){//看看两个人在不在同一集合 fa[find(a[i].x)]=find(a[i].y);//不是则合并 s++; ans+=a[i].z;//累加树边长度 if(s>=n-1){ break; } } } if(s<n-1){ cout<<"orz"<<endl;//不要忘了这个(其实有没有似乎没有关系) return 0; } //输出啥的......不说 :)
大佬勿喷即可qvq
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 复习C++语法--基础篇 2020-05-27
- C++生成随机数 2020-04-18
- 括号生成 2020-04-09
- 迷宫算法 之 迷宫生成和迷宫寻路 2020-03-25
- CTF中特别小的EXE是怎么生成的 2020-03-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash