首页 > 其他分享 >食物链题解

食物链题解

时间:2024-09-15 10:04:43浏览次数:8  
标签:食物链 捕食 int 题解 fa add 天敌 find

双倍经验:P2024 [NOI2001] 食物链

当问题要求维护一些对立的关系时(朋友、敌人),就可以用种类并查集实现。

因为有三种关系所以并查集的数组要开三倍空间,第一倍空间存同类关系,第二倍存捕食关系,第三倍存被捕食关系。

注意:一的猎物的猎物就是一的天敌,其他就可以直接并查集维护即可。

注意这题是多组数据要多测清空

具体判断可以代码,有详细注释,利于理解:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=50005*3;//三倍点 
int n,m;
int fa[N];
//查找 
int find(int x){
	return fa[x]==x?x:find(fa[x]);
}
//合并 
void add(int u,int v){
	int x=find(u);
	int y=find(v);
	fa[x]=y;
}
int main(){
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
    	cin>>n>>m;
		//初始化 
		for(int i=1;i<=3*n;i++){//
			fa[i]=i;
		}
		int ans=0;//注意多测 
		while(m--){
			int x,y,s;
			cin>>s>>x>>y;
			//编号超过n,假话。
			if(x>n||y>n){ 
				ans++;
				continue;
			}
			if(s==1){
				//成为同类但存在捕食关系,假话。 
				if(find(x+n)==find(y)||find(y+n)==find(x)){
					ans++;
				}
				else{
					add(x,y);//同类 
					add(x+n,y+n);//天敌之间也是同类 
					add(x+n+n,y+n+n);//天敌的天敌也是同类 
				}
			}
			else{
				//捕食存在同类和被捕食关系,假话
				if(find(x)==find(y)||find(y+n)==find(x)){
					ans++;
				}
				else{
					add(x+n,y);//x捕食y
					add(x+n+n,y+n);//天敌的捕食 
					add(x,y+n+n);//天敌的天敌也存在捕食关系 
				}
			}
		}
	   	cout<<ans<<"\n";
	}
    return 0;
}

标签:食物链,捕食,int,题解,fa,add,天敌,find
From: https://www.cnblogs.com/sadlin/p/18414998

相关文章

  • [ABC371D] 1D Country 题解
    这题,怎么说呢,\(STL\)大法好。前置芝士:lower_pound函数在结构体上的使用。那其实这题便是一个二分前缀和的水题了。结构体存储每个村庄的距离\(x\),人口\(d\)。对于每个输入的\([l,r]\)二分查找其对应的村庄,进行一次答案的统计,输出即可。代码:#include<bits/stdc++.......
  • 【LGR-200-Div.4】洛谷入门赛 #27 A-H题解
    A#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;mt19937rnd(time(0));#defineintlonglongtypedeftuple<int,int,int>tp;#definexfirst#defineysecondtypedefpair<int,int>pii;typedefpair<double,double>......
  • 题解 [ABC371G] Lexicographically Smallest Permutation(中文/English)
    本题解提供英文版,位于示例代码之后。Englishversionofthiseditorialisprovidedafterthesamplecode.官方题解竟然用Python来算高精度lcm,我来提供一个可以避免一切大整数运算的方法。考察\(u\getsP_u\)这张图的每个置换环。为了使答案字典序最小,显然需要从前往后......
  • P9891 [ICPC2018 Qingdao R] Repair the Artwork 题解
    所求即为选择的区间恰好包含所有\(a_i=2\)的位置的方案数。设所有\(a_i=2\)的位置\(i\)组成集合\(S\),考虑容斥被选中的位置是\(S\)的子集的方案数\(g(S)\)。设\(T\)为\(S\)的子集,\(T\)的贡献\(f(T)\)为:选中的位置都在\(T\)的子集中的方案数乘容斥系数\(......
  • [题解]CF542A Place Your Ad Here
    思路首先因为电视台比广告多一个信息,所以通常来说枚举电视台是更有前途的。因此枚举每一个电视台,考虑所有广告的贡献。对于一个电视台,\(c_i\)是定值,也就是找到所有广告与电视台所表示区间交得最多的那一个。假设枚举的电视台控制了\([L,R]\)区间,则广告\([l,r]\)会有三种方......
  • Luogu P10179 水影若深蓝 题解 [ 绿 ] [ 并查集 ] [ 构造 ]
    水影若深蓝:挺好的一道并查集构造题。观察不难发现“距离为\(2\)”这个条件我们可以通过黑白染色实现,我们把他们的中转点染成与他们相反的颜色,把这两个距离为\(2\)的点染成相同颜色。这个染色问题就很并查集。于是我们用并查集维护相同的种类。显然,当图上只有一个连通块的......
  • 请求HTTP链接的图片等资源被自动变成HTTPS请求的问题解决(顺便可以解决图片防盗链)
    文章目录问题现象问题根本原因常规问题解决办法非Chrome浏览器:控制CSP协议对HTML页面处理nginx配置中处理Chrome浏览器本地处理方式Chrome浏览器通用解决办法(服务器端无法控制新版Chrome这种行为,只能曲线救国--顺便可以解决图片防盗链)网页的网站使用http域名代理服务......
  • P5985 [PA2019] Muzyka pop 题解
    P5985[PA2019]Muzykapop题解是蛮有意思的一道题。\(n\le200\),第一感觉是区间dp,但是又不好设出状态。考虑\(b\)单调递增的过程中的性质,考虑后得到\(b\)的最高含\(1\)的位一定是单调不降的,于是我们考虑将最高的含\(1\)的位设入状态。第一反应是设\(f_{i,j}\)表示......
  • 力扣494-目标和(Java详细题解)
    题目链接:494.目标和-力扣(LeetCode)前情提要:因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。最近刚学完01背包,所以现在的题解都是以01背包问题为基础再来写的。如果大家不懂01背包的话,建议可以去学一学,01背包问题可以说是背包问题的基础。如果大家感兴趣,......
  • 《Civilization: Beyond Earth》启动失败?《文明太空》msvcr110.dll问题解决方案大放送
    当您在尝试启动《文明:太空》(Civilization:BeyondEarth)时遇到“找不到msvcr110.dll”或“msvcr110.dll缺失”的错误提示,这意味着您的计算机上缺少或损坏了MicrosoftVisualC++2012运行时库中的一个关键组件。msvcr110.dll是许多基于C++开发的游戏和应用程序正常运行所必需的......