poj 1182 食物链 //带权并查集

太过爱你忘了你带给我的痛 2022-08-14 02:58 164阅读 0赞

<pre name="code" class="cpp">#include <stdio.h>
    
    int ani[55000], rel[55000];
    
    void init(int n)
    {
    	int i;
    	for(i=0; i<=n; i++)
    	{ ani[i] = i; rel[i] = 0;}
    }
    int findd(int x)<span style="white-space:pre">		</span>//回溯路径压缩，好好理解0.0
    {
    	int fx;
    	if(x == ani[x])		return x;
    	fx = ani[x];
    	ani[x] = findd(fx);
    	rel[x] = (rel[x]+rel[fx])%3;<span style="white-space:pre">	</span>//向量法，高大上 x->y = x->fx + fx->fy + fy->y
    	return ani[x];
    }
    
    int judge(int d, int x, int y, int n)
    {
    	int fx, fy;
    	if( (x>n || y>n) || (x==y && d==1) ) return 0;
    
    	fx = findd(x);
    	fy = findd(y);
    	if( (fx==fy) && ((rel[x]-rel[y]+3)%3 != d) )	return 0;
    	
    	ani[fx] = fy;
    	rel[fx] = (-rel[x] + d + rel[y] +3)%3;	
    	return 1;
    }
    
    int main()
    {
    	int n, k, d, x, y, i;
    	int sum = 0;
    	
    	scanf("%d%d", &n, &k);
    	init(n);
    	
    	for(i=0; i<k; i++)
    	{
    		scanf("%d%d%d", &d, &x, &y);
    		if(!judge(d-1, x, y, n))
    			sum++;
    	}
    	printf("%d\n", sum);
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，164人围观）

还没有评论，来说两句吧...

相关阅读

相关 poj 1182-食物链【并查集】

食物链 <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td>

r囧r小猫/ 2022年08月21日 06:51/ 0 赞/ 164 阅读

相关 poj 1182 食物链 //带权并查集

<pre name="code" class="cpp">include <stdio.h> int ani[55000], rel[55000];

太过爱你忘了你带给我的痛/ 2022年08月14日 02:58/ 0 赞/ 165 阅读

相关并查集（2）--POJ 1182 食物链

食物链 [http://acm.pku.edu.cn/JudgeOnline/problem?id=1182][http_acm.pku.edu.cn_JudgeOnline

拼搏现实的明天。/ 2022年07月15日 08:30/ 0 赞/ 186 阅读

相关 POJ 1182 食物链（并查集+集合有条件合并）

食物链 Description 动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。现有N个动物，以1－N编号。每个动物都是

曾经终败给现在/ 2022年06月13日 14:40/ 0 赞/ 194 阅读

相关 poj-1182 食物链 **

1 // poj1182.cpp 2 // 与 poj-1703 Find them, Catch them 思想类似，只是多了一种状态，rank取值为0

太过爱你忘了你带给我的痛/ 2022年04月10日 08:08/ 0 赞/ 207 阅读

相关 POJ-1182.食物链(并查集)

[1182.食物链][1182.] Description 动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。现有

蔚落/ 2022年03月07日 01:36/ 0 赞/ 232 阅读

相关 POJ 1182食物链————并查集复习

[食物链][Link 1] Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 105782 Acc

ゝ一世哀愁。/ 2021年12月03日 12:09/ 0 赞/ 239 阅读

相关扩展并查集——POJ - 1182

题目含义找出与之前的话不符的假话的数目题目分析简单的扩展并查集题目代码 include<iostream> include<stdio.h>

桃扇骨/ 2021年11月22日 09:28/ 0 赞/ 260 阅读

相关 AcWing-240. 食物链【带权并查集】题解

目录 1.题目 2.思路 1.路径压缩时，如何更新Value

港控/mmm°/ 2021年09月01日 03:16/ 0 赞/ 318 阅读

相关 poj-1182-食物链【带权并查集】题解

目录 1.题目 2.题意 3.思路 4.代码 1.题目动物

布满荆棘的人生/ 2021年08月30日 00:07/ 0 赞/ 402 阅读