首页 > 其他分享 >P2024 [NOI2001] 食物链

P2024 [NOI2001] 食物链

时间:2023-10-18 22:23:00浏览次数:43  
标签:P2024 fx 食物链 int fa NOI2001 ans find unit

P2024 [NOI2001] 食物链

法一:种类并查集
A->B->C->A
[1,n]:表示同类, [n+1,2n]:表示猎物,[2n+1,3*3]:表示天敌

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;
int fa[3 * N];
int find(int x) {
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void unit(int x, int y) {
	int r1 = find(x), r2 = find(y);
	fa[r1] = r2;
}
int main() {
	int n, m;
	cin >> n >> m;
	int ans = 0;
	for (int i = 1; i <= 3*n; i++) fa[i] = i;
	while (m--) {
		int op, x, y;
		cin >> op >> x >> y;
		if (x > n || y > n) { ans++; ; continue; }
		if (op == 1) {
			if (find(x + n) == find(y) || find(y + n) == find(x)) { ans++;; continue; }//x的猎物是y,y的猎物是x
			unit(x, y);
			unit(x + n, y + n);
			unit(x + 2 * n, y + 2 * n);
		}
		else {
			if (find(x) == find(y) || find(y + n) == find(x) || x == y) { ans++; ; continue; }//y与x是同类,y的猎物是x,x==y
			unit(x + n, y);//x的猎物是y的同类,或者说y的同类是x的猎物
			unit(x + n * 2, y + n);//y的猎物是x的天敌
			unit(y + n*2, x);//y的天敌是x
		}
	}
	cout << ans;
	return 0;
}

法二:带权并查集
0:同类,1:天敌,2:猎物
转化:
1.在同一集合中:d[x]=(d[x]+d[fx])%3:如果x1,也就是x吃fx;fx0,也就是fx与祖先同类,所以x吃祖先
2.如果不在同一集合:d[fx]=(d[y]-d[x]+0/1+3)%3:确立两祖先的关系,可能有负数,记得+3

点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;
int fa[N];
int d[N];
int find(int x) {
	if (x != fa[x]) {
		int xx = fa[x];
		fa[x] = find(fa[x]);
		d[x] = (d[x] + d[xx]) % 3;
	}
	return fa[x];
}
int main() {
	int n, m;
	cin >> n >> m;
	int ans = 0;
	for (int i = 1; i <= n; i++) fa[i] = i;
	while (m--) {
		int op, x, y;
		cin >> op >> x >> y;
		if (x > n || y > n || (op == 2 && x == y)) { ans++; continue; }
		int fx = find(x), fy = find(y);
		if (op == 1) {
			if (fx == fy) {
				if (d[x] != d[y])ans++;
			}
			else {
				fa[fx] = fy;
				d[fx] = (d[y] - d[x] + 3) % 3;
			}
		}
		else {
			if (fx == fy) {
				int res = (3 + d[x] - d[y]) % 3;//关系,记得取模
				if (res != 1) ans++;
			}
			else {
				fa[fx] = fy;
				d[fx] = (d[y] - d[x] + 4) % 3;
			}
		}
	}
	cout << ans;
	for (int i = 1; i <= 5; i++) cout << d[i] << ' ';
	return 0;
}

法三:建立三个并查集,分别储存天敌,食物,同类

标签:P2024,fx,食物链,int,fa,NOI2001,ans,find,unit
From: https://www.cnblogs.com/bu-fan/p/17772769.html

相关文章

  • poj 1182 食物链---带权值的并查集
    这题就一组数据,用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>in......
  • P4017 最大食物链计数 (DAG拓扑排序)
    空降锣鼓1题目分析首先,要知道这道题是Topo拓扑排序。不妨先从拓扑排序定义下手,分析题目的性质。经分析得:食物链中的生物——节点生物之间的关系——有向边为了方便描述,我们将不会捕食其他生物的生产者叫做最佳生产者不会被其他生物捕食的消费者叫做最佳消费......
  • Ynoi2001 冷たい部屋、一人 题解
    \(\text{link}\),这题太毒瘤啦!难写难调还略微卡常。谁爱卡常谁卡吧。反正我先贺为敬了。——引用自洛谷别人的提交记录本人写了两天(两个\(case\)各一天),调崩溃了才调出来,太毒瘤了!看到颜色相同发现不弱于\(O(n\sqrtn)\),一眼根号分治,设阈值为\(B\)。case1对于颜色出现次......
  • P4017 最大食物链计数
    \(P4017\)最大食物链计数最大食物链数量;最大指的是需要从一个入度为零的点开始到一个出度为零的点,这是一个完整的食物链,问我们给出的食物网中,食物链的数量①本题中,不仅需要记录一下入度,还要记录一下出度,这是因为我们要计算食物链的数量,食物链的最后一个结点,就是出度为......
  • P4017 最大食物链计数
    P4017最大食物链计数初中生物都忘了,食物链不知道从生产者还是消费者开始了题目给出有向无环图,从入度为零的点(不保证唯一)开始,走到出度为零的点(不保证唯一)共有多少条路径,答案对80112002取模保证:道路单向无重边(A吃B就没有B吃A,也不会自己吃自己)图中无环(不会有A吃B,B吃C,C吃A)思路......
  • [刷题笔记] Luogu P4017 最大食物链计数
    ProblemDescription首先明确,最大食物链指生产者到顶级消费者(即最高营养级),而不是最长的食物链这样,我们就可以将题意转化为:在一张图中,求入度为0的点到出度为0的点路径数量这不妥妥的拓扑排序嘛(这题竟然在dp训练题单里,想了好久的dp)Solution虽说是拓扑排序,但并不完全是。我们......
  • [刷题笔记] Luogu P3183 食物链
    ProblemDescription通俗一点就是在一张图上求入度为0的点到出度为0的点路径的个数。Solution简要题意后发现可以拓扑排序?这里主要介绍记忆化搜索。记忆化搜索是指记住当前节点的状态,待下次搜到这里直接调用即可,无需继续搜索。显然由记忆化搜索延伸到dp,但如果状态设计很复杂......
  • poj 1182 食物链 并查集
    食物链TimeLimit:1000MSMemoryLimit:10000KTotalSubmissions:56297Accepted:16500Description动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B,B吃C,C吃A。现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种......
  • P2024 [NOI2001] 食物链 || #576. 食物链【NOI2001】 (并查集)
    空降锣鼓空降OJ题解:#include<bits/stdc++.h>usingnamespacestd;intn,k;intd,x,y;intans;intfa[500050];intfind(intx){//找爸爸 if(fa[x]==x) returnfa[x]; returnfind(fa[x]);}intmain(){ cin>>n>>k; for(inti=1;i<=n*3;i++)//开三个并查集风......
  • POJ 1182 食物链
    解题思路:并查集经典中的经典题,在网上看了很多大牛的思路,大部分是增加一个结构体存动物间的关系,结合并查集判断,但是关系域的更新比较复杂,一下子不太容易理解。所以就有人另开思路,这里介绍一个十分巧妙的思路。一般我们都会把一个动物当成一个节点,然后去执行并查集等操作。但是有位大......