首页 > 其他分享 >最小生成树板子

最小生成树板子

时间:2023-03-10 13:33:07浏览次数:32  
标签:return int 最小 生成 板子 find

 

#include <bits/stdc++.h>
using namespace std ;
 	const int N=5003,M=2e5+2;
 int f[N],n,m;
 struct E{
 	int x,y,z;
 }e[M];
 int find(int x){
 	return x==f[x]?x:f[x]=find(f[x]);
 }
 int cmp(E x,E y){
 	 return x.z<y.z;
 }
 void krus(){
 	 sort(e+1,e+1+m,cmp);
 	 int i,x,y,fx,fy,z,c=0,s=0;
 	 for(i=1;i<=n;i++) f[i]=i;
 	 
 	 for(i=1;i<=m;i++){
 	 	x=e[i].x,y=e[i].y,fx=find(x),fy=find(y);
 	 	if(fx!=fy){
 	 	   f[fx]=fy;
 	 	   c++,s+=e[i].z;
 	 	   
 	 	   if(c==n-1) break;
 	 	}
 	 }
 	 cout<<s<<endl;
 } 
 signed main(){
 	int i,x,y,z;
 	 cin>>n>>m; 
	  for(i=1;i<=m;i++) cin>>e[i].x>>e[i].y>>e[i].z;
	krus();
 }

 
 

 

标签:return,int,最小,生成,板子,find
From: https://www.cnblogs.com/towboa/p/17203040.html

相关文章

  • vue3 二次封装element-plus的弹框el-dialog,增加了最小化、弹出位置 title字体色、hea
    一、利用一个小时简单二次封装了element-plus的弹框el-dialog,根据项目需求主要增加了最小化、最小化icon、弹出位置、title字体色、header背景色、关闭图标色。 代码如......
  • 生成器总结
    生成器1、生成器对象的本质生成器对象其实本质上就是迭代器对象,内置有双下__iter__和__next__方法2、区别迭代器对象就是Python解释器提供的各种数据类型或是文件......
  • 利用ai生成深度图后实现图片跟随鼠标实现3D效果
    实现原理利用three.js根据深度图来控制不同深度位置像素位移距离不同,营造3D效果。 前期准备深度图生成网站 LeiaPixConverter注册登录完成后第一步点击upload上传......
  • Python迭代与生成器
    1、迭代_iter_对象方法可迭代对象,返回迭代器__next_对象方法迭代器对象,返回迭代中每一步的运算iter(object)内置函数得到object的迭代器next(object)......
  • 生成器,迭代器
    迭代器迭代器分为迭代器对象和可迭代对象,迭代就是每一次的结果都必须依赖于上一次的结果,能够通过for循环进行迭代操作,也能够通过__next__方法进行迭代操作可迭代对象内......
  • 关于字典-用反射将字典动态生成枚举
    在Java中,枚举(enum)的值是在编译时固定的。因此,不能直接基于字典动态生成枚举。但是,可以使用Java的反射机制来实现类似的效果。以下是一个简单的示例importjava.lang.refl......
  • 最小表示法
    思路考虑将原串复制一遍,就可以得到所有循环同构串,然后先枚举两个位置\(i,j\),分别对应第一个和第二个位置。然后往后枚举,遇到第一个不同的位置,那么另外一个大的数对应的......
  • C#使用NPOI生成Word文档的方法
    在此我们介绍以模板方式载入内容导出Word文档一、获取模板(XWPFDocumentdoc)1.首先获取模板,然后把获取的模板实例化为NPOI的文档对象进行操作:FileStreamstream=File.O......
  • 戴尔R750服务器 安装 ubuntu 22.04 最小话安装后 初始化设置
    1.设置root密码sudopasswdroot显示如下先输入test的密码之后输入root需要设置的密码2次[sudo]passwordforccpit:Newpassword:Retypenewpassword:passwd:p......
  • Visual Studio生成的exe程序自动要求以管理员身份运行
    在exe工程属性页下-》Linker-》UACExecutionLevel-》requireAdministrator: 配置好后,再次启动调试会弹出下面的框,重启以管理员身份运行VisualStudio:生成的exe也会......