首页 > 其他分享 >poj 1182 食物链---带权值的并查集

poj 1182 食物链---带权值的并查集

时间:2023-09-12 12:38:15浏览次数:31  
标签:d% int 带权值 sum 查集 1182 else fa root


这题就一组数据,用while(scnaf(“%d%d”,&n,&m)!=EOF)..就wa了,我wa了数次,无语了。。

带权值的并查集,

d[]数组存的是每个点和根节点的关系,同类为d[i]=0;  根节点 吃 i点为d[i]=1;  i点吃根节点为d[i]=2;

自己画图感受一下吧!!

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int f[50050],d[50050];
int root(int p)
{
	if(f[p]==-1) return p;
	else {
		int fa=f[p];
		f[p]=root(f[p]);//递归先找d[fa],下一步d[p]=(d[p]+d[fa])%3;才能执行
		d[p]=(d[p]+d[fa])%3;
		return f[p];
	}
}
void merge(int a,int b,int c)
{
	int aa=root(a);
	int bb=root(b);
	f[bb]=aa;
	d[bb]=(d[a]-d[b]+c+3)%3;
}

int main()
{
	int i,j,k;
	int n,m;
	scanf("%d%d",&n,&m);
		int a,b,c,sum=0;
		memset(d,0,sizeof(d));
		memset(f,-1,sizeof(f));
		while(m--){
			scanf("%d%d%d",&a,&b,&c);
			if(b>n || c>n) sum++;
			else{
				if(a==1){
					if(root(b)!=root(c))
						merge(b,c,0);
					else if(d[c]!=d[b]) sum++;
				}
				else{
					if(root(b)!=root(c))
						merge(b,c,1);
					else if(((d[c]-d[b]-1)%3)!=0) sum++;
				}
			}
		}
		printf("%d\n",sum);
}




标签:d%,int,带权值,sum,查集,1182,else,fa,root
From: https://blog.51cto.com/u_16244339/7444295

相关文章

  • hdu-3926-Hand in Hand-并查集
    判断两个图是否同构。。用了并查集。。#include<stdio.h>#include<string.h>#include<stdlib.h>#include<algorithm>#include<queue>#include<stack>usingnamespacestd;#definelllonglongintn,m;structnode{ intfu; intsum; intf......
  • 并查集 堆排序 (9/10)
    并查集模板 注意查找到后查找的节点直接连接根节点#include<iostream>usingnamespacestd;constintN=100010;intp[N];//关键记住find函数intfind(inta){if(p[a]!=a)p[a]=find(p[a]);//不等于根节点就往头结点走,并且等于returnp[a];}intma......
  • (测试)带权并查集
    带权并查集普通的并查集只能维护每个节点所在集合的编号,带权并查集则可以维护集合内任意一点到所在集合根的距离。带权并查集是结点存有权值信息的并查集。相比于一般的并查集,带权并查集需要开辟两个数组:一个是dsu[N],用来判断集合关系;一个是dis[N],用来描述其与根节点的关系。当......
  • [kuangbin带你飞]专题五 并查集
    WirelessNetwork POJ-2236 题意:n台电脑,坐标(x,y),电脑通讯范围为d;一开始,给出所有电脑坐标,然后所有电脑初始状态都是坏的,题目输入两个操作,第一修电脑且这台电脑可对d范围内正常电脑进行通讯了;第二就是查询,两台电脑是否可以通讯?算法:并查集思路:第一次,我直接通过坐标判断,那些电......
  • Cross Swapping CFE (并查集正负集合)
     思路:把每个草做抽象为点, 观察性质:图中对称的2个点,要交换,可以通过2种的操作方式得到, 2个操作异号, 反之2个操作同号通过+-表示和祖父是什么关系,通过并查集来看看当前有没有在同一个集合里面. ......
  • 2023牛客暑期多校练营6 A-Tree 树上背包+并查集
    2023牛客暑期多校练营6A-Tree树上背包+并查集题目链接题意:给出一棵树,节点为黑色或者白色,定义整棵树的贡献为,任意白点到任意黑点所经过路径上的最大边权之和,节点i原本颜色已给出,可以花费c[i]代价翻转节点i的颜色,问最大贡献是多少。做法:首先我们思考怎么处理最大边权的问题......
  • 并查集
    将两个集合合并询问两个元素是否在一个集合当中基本原理:每个集合用一棵树表示,树根的编号就是整个集合的编号。每个节点储存它的父节点,p[x]表示x的父节点判断树根(属于那个集合)if(p[x]==x)求x的集合编号:while(p[x]!=x)x=p[x];合并两个集合:px是x的集合编号,py是y的集合......
  • 并查集
    2023.8.26很晚了,还来得及吗 2023-08-2621:18:03P2661[NOIP2015提高组]信息传递-洛谷|计算机科学教育新生态(luogu.com.cn)还未完成 2023-08-2708:21:06已完成  初步总结:主要分为三个模块:合并,查找,移动(还不会)注意:合并时,是把根节点合并,而非自身优化:r......
  • hdu:畅通工程(并查集)
    ProblemDescription某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路?Input测试输入包含若干......
  • 并查集学习笔记
    并查集的定义并查集是一种树型的数据结构,用于处理一些不相交集合(disjointsets)的合并及查询问题。常常在使用中以森林来表示。——百度百科并查集,顾名思义,支持以下两种操作操作:并(Union):把两个不相交的集合合并为一个集合。查(Find):查询两个元素是否在同一个集合中。并......