POJ 1182 食物链(并查集拆点)
2024-10-21 06:18:02
【题目链接】 http://poj.org/problem?id=1182
【题目大意】
草原上有三种物种,分别为A,B,C
A吃B,B吃C,C吃A。
1 x y表示x和y是同类,2 x y表示x吃y
问给出的信息有几条是和前面相违背的
【题解】
之前这道题是用加权并查集做的,做的有些晕晕乎乎,现在换了种思路做就清晰很多了
将每个点拆点,比如x拆为,x-A,x-B,x-C
表示x属于A类,x属于B类,和x属于C类,
如果y和x属于同类,那么合并x-A和y-A,x-B和y-B,x-C和y-C
如果是x吃y的情况,那么合并x-A和y-B,x-B和y-C,x-C和y-A
也就是说将x属于A这种类型的条件作为节点进行并查集运算
就能很轻松地解决这种问题
【代码】
#include <cstdio>
const int N=50010*3;
int f[N],n,k,ans=0,op,x,y;
void init(int n){for(int i=0;i<=n;i++)f[i]=i;}
int sf(int x){return f[x]==x?x:f[x]=sf(f[x]);}
bool Same(int x,int y){return sf(x)==sf(y);}
bool Union(int x,int y){f[sf(x)]=sf(y);}
int main(){
scanf("%d%d",&n,&k);
init(3*n);
for(int i=1;i<=k;i++){
scanf("%d%d%d",&op,&x,&y);
if(--x<0||x>=n||--y<0||y>=n){ans++;continue;}
if(op==1){
if(Same(x,y+n)||Same(x,y+2*n))ans++;
else{Union(x,y);Union(x+n,y+n);Union(x+2*n,y+2*n);}
}else{
if(Same(x,y)||Same(x,y+2*n))ans++;
else{Union(x,y+n);Union(x+n,y+2*n);Union(x+2*n,y);}
}
}printf("%d\n",ans);
return 0;
}
最新文章
- fuse入门
- gedit脚本
- MQTT实现长连接,IM最简单实例
- hdu4691 Front compression ——暴力 || 后缀数组
- 【Windows 10 IoT - 2】LED闪烁及动画绘制(树莓派 Pi2)
- 利用File类过滤器列出目录下的指定目录或文件
- ABAP版连连看
- matlab绘图+计算心得
- ADB not responding. You can wait more,or kill"abd.exe" process manually and click 'Restart'
- ORACLE【2】:锁机制及解锁
- 【算法】最长公共子序列(nlogn)
- android玩耍(-) adbshell安装
- DB2表是否存在
- python中的函数对象与闭包函数
- Linux显示PCI设备
- java第二章总结与感想
- Python开发——15.协程与I/O模型
- powerdesigner 使用技巧 建模工具 导出sql 导出实体类 导出word
- Python while 循环
- Python中=、copy、deepcopy
热门文章
- Django学习(一) Django安装配置
- HDU1043 Eight(BFS)
- python操作redis-事务
- Nginx 配置指令的执行顺序(一)
- VirtualBox 上安装CentOS 6.5
- poj 1094 Sorting It All Out_拓扑排序
- vsftpd配置---------------------之chroot_local_user和chroot_list_enable含义
- kindeditor 下图片链接取消边框
- PhoneGap或者Cordova框架下实现Html5中JS调用Android原生代码
- DoNet开源项目-基于Amaze UI的点餐系统