1300*C. Rumor(并查集贪心)

news/2024/7/15 19:18:46 标签: c语言, 图论, 开发语言, 数据结构, 算法, c++

解析:

        并查集,求每个集合的最小费用。

         每次合并集合的时候,根节点保存当前集合最小的费用。 

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int n,m,a[N],p[N],cnt[N];
int find(int x){
	return x==p[x]?x:p[x]=find(p[x]);
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		p[i]=i;
	}
	while(m--){
		int x,y;
		scanf("%lld%lld",&x,&y);
		x=find(x),y=find(y);
		if(a[x]<=a[y]) p[y]=x;
		else p[x]=y;
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(i==p[i]) ans+=a[i];
	}
	printf("%lld",ans);
	return 0;
}

http://www.niftyadmin.cn/n/5064775.html

相关文章

Linux CentOS7 vim多窗口编辑

我们在用vim编辑文件时&#xff0c;有各种需求。如有时需要在多个文件之间来回操作&#xff0c;一会关闭一个文件&#xff0c;一会再打开另外一个文件&#xff0c;这样来回操作显得太笨拙。有时&#xff0c;vim编辑多行的大文件&#xff0c;来回查看、编辑前面一部分及最后一部…

队列的基本操作(数据结构)

队列的顺序实现 #include <stdlib.h> #include <iostream> #include <stdio.h>#define MaxSize 10//定义队列的长度typedef struct{int front,rear;int data[MaxSize]; }SqQueue;//初始化队列 void InitQueue(SqQueue &Q){Q.frontQ.rear0; } //判断队列…

数据的加解密

文章目录 分类特点业务的使用补充 分类 对称加密算法非对称加密算法 特点 对称加密算法 : 加密效率高 !加密和解密都使用同一款密钥 但是有一个问题 : 密钥如何从服务端发给客户端? (假如你直接先将密钥发给对方,要是在过程中被黑客技术破解了,那后面的消息也就泄漏了) (后…

十四天学会C++之第三天(数组和字符串)

1. 数组的定义和初始化 数组是一种由相同数据类型的元素组成的集合&#xff0c;这些元素按照一定的顺序存储在连续的内存位置上。数组的大小在创建时是固定的&#xff0c;无法在运行时改变。 在C中&#xff0c;数组的定义和声明非常简单。定义一个数组&#xff1a; 数据类型…

华为云云耀云服务器L实例评测 | 实例场景体验之搭建接口服务:通过华为云云耀云服务器构建 API 服务

华为云云耀云服务器L实例评测 &#xff5c; 实例场景体验之搭建接口服务&#xff1a;通过华为云云耀云服务器构建 API 服务 介绍华为云云耀云服务器 华为云云耀云服务器 &#xff08;目前已经全新升级为 华为云云耀云服务器L实例&#xff09; 华为云云耀云服务器是什么华为云云…

WebExceptionHandler详解

WebExceptionHandler 是 Spring Framework 中的一个接口&#xff0c;它用于处理 Web 应用程序中的异常。具体来说&#xff0c;WebExceptionHandler 主要用于处理在处理 HTTP 请求时可能发生的异常&#xff0c;并返回适当的响应给客户端。 在 Spring 框架中&#xff0c;WebExce…

junit @ExcludePackages排除多个包

在JUnit中&#xff0c;可以使用ExcludePackages注解来排除多个包。该注解可以用在测试类或测试方法上。 如果要排除多个包&#xff0c;可以在ExcludePackages注解的value属性中使用数组来指定要排除的包名。例如&#xff0c;要排除包com.example.package1和com.example.packag…

快速上手Apache POI

哈喽~大家好&#xff0c;这篇我们来看看快速上手Apache POI。 &#x1f947;个人主页&#xff1a;个人主页​​​​​ &#x1f948; 系列专栏&#xff1a;【日常学习上的分享】 &#x1f949;与这篇相关的文章&#xff1a; Red…