POJ 2492 A Bug's Life (带权并查集 && 向量偏移)
2024-09-04 05:22:33
题意 : 给你 n 只虫且性别只有公母, 接下来给出 m 个关系, 这 m 个关系中都是代表这两只虫能够交配, 就是默认异性, 问你在给出的关系中有没有与异性交配这一事实相反的, 即同性之间给出了交配关系。
分析 : 本题雷同POJ 1182 食物链, 如果会了那一题, 那现在这题便简单多了, 建议先了解食物链的偏移向量做法。这里也是使用向量的思考方式来进行relation的变化, 这里我令 relation = 0为同性, relation = 1为异性, 接下来的步骤就和食物链的雷同了。
优化 :
① 因为关系的值只有0 或 1, 这里可以考虑位运算中的异或来加快relation变化的运算。
② 由于给出的输入很多, 所以可以采用读入挂来加快读入速度。
瞎搞 : 一开始计算关系的时候居然去%1, 失策啊, 要将范围控制在[0, n]之间的话就应该%(n+1)。还有在判断是否矛盾时候, 实际只要判断两个虫的relation是否一样即可, 我还在加减乘除模来模去=_=
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> using namespace std; ; int f[maxn], relation[maxn], n, num; inline int Scan() { , ch; bool flag = false; if((ch=getchar()) == '-') flag = true; '; +ch-'; return flag?-res:res; } inline void initialize() { ; i<=n; i++){ relation[i] = ; f[i] = i; } } int findset(int x) { if(f[x] == x) return x; int father = f[x]; f[x] = findset(father); relation[x] = relation[father]^relation[x]; //同 relation[x] = ( relation[father] + relation[x] )%2; return f[x]; } int main(void) { int nCase; nCase = Scan(); ; while(nCase--){ bool flag = true; n = Scan(); num = Scan(); initialize(); while(num--){ int a, b; a = Scan(); b = Scan(); if(!flag) continue; if(a==b){ flag = false; continue; } int root_a = findset(a); int root_b = findset(b); if(root_a != root_b){ f[root_b] = root_a; relation[root_b] = relation[a]^^(-relation[b]); //同 relation[root_b] = ( relation[a] + 1 - relation[b] )%2; }else{ if(relation[a]==relation[b]) flag = false; //同 if( (-relation[a]+relation[b]+2)%2 != 1) flag = false; } } if(!flag){ printf("Scenario #%d:\nSuspicious bugs found!\n", ++t); }else{ printf("Scenario #%d:\nNo suspicious bugs found!\n", ++t); } puts(""); } ; }
最新文章
- 办公大楼3D指纹门禁系统解决方案
- 身份证校验,前台js校验,后台java校验
- ASP.NET Web API Help Pages using Swagger
- jquery中dom元素的attr和prop方法的理解
- sql server2008中左连接,右连接,等值连接的区别
- Adivisor
- 爪哇国新游记之三十四----Dom4j的XPath操作
- Sql Server中通配符的使用
- Android系统在新进程中启动自定义服务过程(startService)的原理分析
- C++中类的public,private,protected比较
- C# send mail with outlook and word mailmerge
- [转载]VS2012创建MVC3项目提示错误: 此模板尝试加载组件程序集 “NuGet.VisualStudio.Interop, Version=1.0.0.0, Culture=neutral, PublicKeyToken=b03f5f7f11d50a3a”。
- 用PL0语言求Fibonacci数列前m个中偶数位的数
- 关于CSRF的攻击
- 团队作业八——第二次团队冲刺(Beta版本)第3天
- C#中的DBNull、Null、""和String.Empty
- vue项目报错webpackJsonp is not defined
- 009_一行python重要工具
- C#泛型创建实例
- MongoDB硬件及开发标准规范
热门文章
- 【计算机视觉】【图像处理】【VS开发】【Qt开发】opencv之深拷贝及浅拷贝,IplImage装换为Mat
- CF650A Watchmen(STL+map)
- MySQL出现 Access denied for user &#39;root&#39;@&#39;localhost&#39; (using password:YES) 解决办法
- yii报错yii\web\Request::cookieValidationKey must be configured with a secret key.
- 动态代理之JDK 和 CGLIB
- 4种vue当中的指令和它的用法
- jQuery改变元素class属性
- [PyQt5]动态显示matplotlib作图(一)
- (转)linux chattr lsattr 命令
- 引用vector里的元素被删除后,引用会怎么样?