首页 > 其他分享 >并查集 How many tables(hdu 1213) How many answers are wrong(hdu 3038)

并查集 How many tables(hdu 1213) How many answers are wrong(hdu 3038)

时间:2024-11-10 21:46:22浏览次数:3  
标签:hdu set int many 查集 roota rootb How 集合

目录

前言

并查集

   并查集的初始化

   并查集的合并

   并查集合并的优化,路径压缩

How many tables(hdu 1213)

   问题描述

   输入

   输出

问题分析

代码

带权并查集

How many answers are wrong(hdu 3038)

   问题描述

   输入

   输出

问题分析

代码


前言

        感觉并查集总共有两个应用,一是解决有关群的问题,二是利用并查集构造一个只有叶子的高效权值树。比方说a和b是朋友b和c是朋友,那么a,b,c这三个人在并查集中就属于同一个集合,如果经过路径压缩后a,b,c三个人的集合就会指向一处

并查集

   并查集的初始化

        最开始初始化并查集时,每个元素的都代表一个独立的集,注意是独立的集,集合间不存在包含和被包含关系,如果是用数组实现我们一般习惯set[i] = i,来表示,也就是元素i的集合被初始化为集合i,这里虽然集合和元素名字相同,但代表的是不同的涵义

   并查集的合并

        并查集的合并操作有点像链表的链接,每个节点都有一个data域和指向其所属集合的指针域,比方说如果要把1集合合并到2集合,那么只需要将1集合的指针域指向2集合即可,再让2集合合并到3集合重复操作,经过一系列操作我们就会发现我们得到了一个1,2,3,4,5的链表。

        感觉有哪里不对吧,我们使用并查集是为了使得算法更加高效,但这样操作好像还不如直接使用一个数组呢,其实这和我们的连接方式有关,注意到每次我们链接的时候都是将大的集合链接到小的集合之上,导致我们连接的结果形成了一棵单支树,但如果把小集合合并到大集合上那么就会实现一颗比较好的多支树,如何避免变成单只树呢?

   并查集合并的优化,路径压缩

        前边说到如果都将大集合合并到小集合之上那么会使得形成的树深度非常深,那么不然就在合并的时候优化一下不就行了呗,不妨在合并操作的时候设计一个变量记录合并之后集合的深度,之后每一次合并的时候都判断一下,保证将小集合合并到大集合中。

        但其实上述还可以优化,并查集主要用处就是给定一个元素,可以快速找到他所处的集合,那么如果并查集所形成的树只有叶子节点那么这不就极大提高了算法效率吗,所以又想出了路径压缩的算法。主要算法思想就是在搜索元素所处的集合的同时将路径上的元素全部直接与集合相连,设计递归的思想,需要仔细理解。

int find_set(int x) {
	if (x != s[x]) s[x] = find_set(s[x]);
	return s[x];   //if(x==s[x]) return s[x];   //效果相同
}

        普通的并查集主要解决分类的问题,下面我们来看一道题。

How many tables(hdu 1213)

hdu 1213

   问题描述

        有一群人去聚会,好朋友之间会坐一桌,规定朋友的朋友也是朋友,问最少需要几桌。

   输入

        第一行输入一个整数T,代表有T个测试,对于每个测试第一行输入两个整数N,M,N代表参会人的编号,之后的M行中每行输入两个整数A,B代表编号A,B两个人为好朋友。

   输出

        对于每个测试输出一行做为答案。

问题分析

        这是一个恒明显的并查集的应用,涉及到分类的问题。

代码

#include<iostream>
using namespace std;
const int E = 1050;

int s[E+1];
int height[E+1];

void init_set() {
	for (int i = 1; i <= E; i++) {
		s[i] = i;
	}
}

int find_set(int x) {
	if (x != s[x]) s[x] = find_set(s[x]);
	return s[x];   //if(x==s[x]) return s[x];   //效果相同
}
/*height[i] = 0;
void merge_set(int a, int b) {
	int roota = find_set(a), rootb = find_set(b);
	if (height[roota] == height[rootb]) {
		s[roota] = rootb; //把a集合接到b上
		height[rootb] += 1;
	}
	else {
		if (height[roota] > height[rootb]) s[rootb] = roota;
		if (height[roota] < height[rootb]) s[roota] = rootb;
	}
}*/

void merge_set(int a, int b) {
	int roota = find_set(a), rootb = find_set(b);
	if (roota != rootb) {
		s[roota] = rootb;
	}
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		init_set();
		int N, M,A,B;
		cin >> N >> M;
		for (int i = 1; i <= M; i++) {
			cin >> A >> B;
			merge_set(A, B);
		}
		int ans = 0;
		for (int i = 1; i <= N; i++) {
			if (s[i] == i) ans++;
		}
		cout << ans << endl;
	}
}

        下面我们来介绍并查集的另一个应用——带权并查集

带权并查集

        想象一个场景,我需要求一个地方到达目的地的距离,但我只知道到途径的几个地方的距离,如何快速得到想要的答案?再回顾我们所说的并查集,它可以很快的查询到节点到根节点,也就是可以迅速查询到所属的集合,那么根据这个特性,给并查集加上权值,这个权值可以是距离,或者是其他的关系,那么就可以迅速查到与根节点的距离(或其他关系)

        这样说可能还是不大形象,下面我们更具一道具体的例题来理解。

How many answers are wrong(hdu 3038)

hdu 3038

   问题描述

        给定几个区间和,试判断对于某个区间和,在前面正确的区间和的基础上,这个区间和是否为真,输出所有假区间和的个数。

   输入

        有多个测试,对于每个测试,第一行输入两个整数n,m,代表有n个整数m组数据,之后的m行中每行输入三个整数a,b,v,代表左闭右闭区间【a,b】区间和为v

   输出

        对于每个测试,输出发生冲突区间和的个数。

问题分析

        本题的区间和其实可以抽象为距离,为了便于理解,我们就抽象为距离哈。

        前面说到使用并查集可以快速找到当前节点与根节点的距离,那么能不能利用这个特性解决这个问题呢,要判断这个节点是否与前面的节点发生冲突,如果前面的节点我都改为到根节点的距离那么想利用前面的节点推算给定区间和只需要这样【a,b】=【a,root】-(b,root】即可,但是会发现这几个区间的表示形式不对,那么我不妨都改为左开右闭区间即:

                                                  [a+1,b] = (a,b】= (a,c】- (b,c】

        值得注意的是每次加入节点的时候还需要更新节点的权值为它到根节点的距离

void init_set() {
	for (int i = 1; i <= E; i++) {
		s[i] = i;
		d[i] = 0;
	}
}

int find_set(int x) {
	if (x != s[x]) {
		int t = s[x];
		s[x] = find_set(s[x]);
		d[x] += d[t];  //注意这里是递归式,到了根节点才会开始累加
	}
	return s[x];   //if(x==s[x]) return s[x];   //效果相同
}

        本题最后的要点就是在两个集合合并的时候如何处理两个根节点之间的权值,我们不如用小学数学知识算一下

  • (a,b]                          距离v
  • (b,rootb]                      距离d[b]
  • (a,roota]                      距离d[a]
  • 要求(roota,rootb]        距离d[roota]
  • 因为                   (a,roota] - (b,roota] = (a,b] 
  • 那么                   (b,roota] = (a,roota] - (a,b]
  • 那么                   (b,rootb] - (roota,rootb] = (b,roota]
  • 则                    (roota,rootb] = (b,rootb] - (b,roota]
  • 即                      (roota,rootb] = (b,rootb] - (a,roota] + (a,b]
  •                       d[roota] = d[b] -d[a] + v

        怎么样,很神奇吧,应该没有绕晕吧。。。。。,

那么接下来就可以开始编代码了

代码

#include<iostream>
using namespace std;
const int E = 200010;

int s[E + 1];
int d[E + 1];  //d[i]代表区间(i,root]的区间和
int ans = 0;

void init_set() {
	for (int i = 1; i <= E; i++) {
		s[i] = i;
		d[i] = 0;  //初始化距离为0
	}
}

int find_set(int x) {
	if (x != s[x]) {
		int t = s[x];
		s[x] = find_set(s[x]);
		d[x] += d[t];  //注意这里是递归式,到了根节点才会开始累加
	}
	return s[x];   //if(x==s[x]) return s[x];   //效果相同
}

void merge_set(int a, int b, int v) {
	int roota = find_set(a), rootb = find_set(b);
	if (roota == rootb) {
		if ((d[a] - d[b]) != v) ans++;
	}
	else {
		s[roota] = s[rootb]; //将a所在的树接到b上
		d[roota] = d[b] - d[a] + v;  //更新a的根节点到b的根节点之间的距离
	}
}

int main() {
	int n, m,a,b,v;
	while (cin >> n >> m) {
		init_set();  //千万不要忘记初始化了,错了几次了,真服了我自己
		while (m--) {
			cin >> a >> b >> v;
			a--;
			merge_set(a, b, v);
		}
		cout << ans << endl;
	}
	return 0;
}

标签:hdu,set,int,many,查集,roota,rootb,How,集合
From: https://blog.csdn.net/2301_80093604/article/details/143663289

相关文章

  • Linux中关于useradd、chmod、chown、getfacl、setfact等权限设置
    文章目录一、Linux用户管理1、用户(user)、用户组(group)、其他用户概念(other)1.1理解Linux的`单用户多任务`,`多用户多任务`概念1.2用户(user)和用户组(group)概念;查看主机名和修改主机名需要root权限(然后输入密码)2.1创建用户2.1.1用adduser创建用户3、删除用户查看用户列......
  • POLIR-Society-Organization-Management: “How”-关系网络+组织建设+目标: 计划:管人:
    POLIR-Society-Organization-Management:“How”沟通+关系网络Object的Role:Internalboss/上级:Outcome,平级:Team/Organization员工:RoleExternalCustomer:7P+RelationshipSupplierCompetetorIndividualGovernment组织建设分辨好坏对错是非目......
  • CF2023D - Many Games
    HDK:他妈的,这个看着也不像2900啊,为啥控我这么久lbtl:他不控你这么久不就不是2900了吗暴力一个比较明显的暴力思路是,如果我们钦定选定的物品的价值,那么可以比较容易地由背包DP算出能达到这个钦定值的最大概率从\([0,\sumw_i]\)枚举所有可能的价值,暴力跑若干次背包,可......
  • linux部署本地测试服务器,部署showdoc,并挂载额外硬盘用于windows共享文件
    过程中坑还是挺多的,在这里做个记录,方便他人也方便自己一、安装linux系统下载镜像使用rufus制作启动盘(linux系统不能使用大白菜等软件)更改网络配置(ifcfg-ens33是网卡名,看个人主机配置而定)vi/etc/sysconfig/network-scripts/ifcfg-ens33将ONBOOT="no"改为ONBOOT=“yes......
  • 【Oracle】How Do Indexes Become Unusable
    遇到的场景:Oracle数据库的分区表出现UNUSABLEINDEX,下述文档用于解决相关问题。SymptomsDescriptionofwhichoperationsmarkindexpartitionsasINDEXUNUSABLE.描述那些操作使得索引不可用CauseTherearesixtypesofmaintenanceoperationsandaddingapartition......
  • ctfshow(316)--XSS漏洞--反射性XSS
    Web316进入界面:审计显示是关于反射性XSS的题目。思路首先想到利用XSS平台解题,看其他师傅的wp提示flag是在cookie中。当前页面的cookie是flag=you%20are%20not%20admin%20no%20flag。但是这里我使用XSS平台,显示的cookie还是这样,并不能得到flag。该方法先作罢。于是......
  • ctfshow(162)--文件上传漏洞--远程文件包含
    Web162进入界面:思路先传个文件测试一下过滤:过滤了特别多符号,注意过滤了点.我们的思路还是要先上传.user.ini文件://修改前GIF89aauto_prepend_file=shell.png//由于过滤了点,所以修改为GIF89aauto_prepend_file=shell上传.user.ini文件接下来就是上传包含一......
  • ctfshow(94,95)--PHP特性--strpos函数
    建议先学习intval函数相关内容Web94源代码:include("flag.php");highlight_file(__FILE__);if(isset($_GET['num'])){$num=$_GET['num'];if($num==="4476"){die("nonono!");}if(preg_match("......
  • 题解:HDU5628 Clarke and math
    数学题可爱捏~HintAnalysis注意到形式很好看,猜测是某种神奇迭代。考虑特殊情况\(k=1\),于是有:\(g(i)=\sum_{i_1\midi}f(i_1)=(f*1)(i)\)$即\(g=f*1\)。于是猜测\(g=f*1^k\),这里的幂运算表示多次Dirichlet卷积。简单证明一下,采用数学归纳法:基本情况\(k=1\),已经证过,......
  • How to Install psql on Mac
    参考链接:Here#firststep➜brewinstalllibpq==>Downloadinghttps://mirrors.ustc.edu.cn/homebrew-bottles/api/formula.jws.json==>Downloadinghttps://mirrors.ustc.edu.cn/homebrew-bottles/api/cask.jws.json==>Fetchingdependencie......