好贷网好贷款

poj 1182 食物链(关系并查集)

发布时间:2016-12-5 22:37:45 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"poj 1182 食物链(关系并查集)",主要涉及到poj 1182 食物链(关系并查集)方面的内容,对于poj 1182 食物链(关系并查集)感兴趣的同学可以参考一下。

http://poj.org/problem?id=1182 思路:是poj 1703的简化版。 p[ x ]表示x的根节点,r[ x ]表示p[ x ]与x的关系。r[ x ] = 0表示p[ x ]与x同类,r[ x ] = 1表示p[ x ]吃x,r[ x ] = 2表示x吃p[ x ]。 find(x)函数:找x的根节点,同时在这一过程中求出r[ x ] = ( r[ x ] + r[  tmp ] )%3。r[ x ] 表示x与未压缩父亲tmp的关系,r[ tmp]表示未压缩父亲tmp与压缩后父亲的关系,那么x与压缩后父亲的关系就是( r[ x ] + r[  tmp ] )%3。 merge(x, y,d):合并x的根节点和y的根节点,d表示x与y的关系。注意合并之后被合并节点的r[ ]值要发生变化。若有p[ fx ] = fy, 那么r[ fx ]要发生变化,因为r[ ] 值表示的是它与根节点的关系。由下图知r[ fx ] = (3 - r[ x ] + d + r[ y ])%3。  判断k个说法是真是假: 若find(x) != find(y),无法判断是真是假,合并x,y,注意他们的关系是d-1。 若相等,就可以判断真假。由下图直接判断(r[ x ] + 3 - r[ y ])%3 是否等于 d-1。不等就是假。 #include <stdio.h> #include <string.h> const int maxn = 50010; int n,m; int p[maxn]; int r[maxn]; void make_set() { for(int i = 1; i <= n; i++) { p[i] = i; r[i] = 0; } } int find(int x) { if(x == p[x]) return x; int tmp = p[x]; p[x] = find(p[x]); r[x] = (r[x] + r[tmp])%3; return p[x]; } void merge(int x, int y, int d) { int fx = find(x); int fy = find(y); p[fx] = fy; r[fx] = (r[y]-r[x]+3+d)%3; } int main() { int d,x,y; int ans = 0; scanf("%d %d",&n,&m); make_set(); while(m--) { scanf("%d %d %d",&d,&x,&y); if(x > n || y > n) { ans++; continue; } if(d == 2 && x == y) { ans++; continue; } int fx = find(x); int fy = find(y); if(fx == fy) { if( (r[x]+3-r[y])%3 != d-1) ans++; } else merge(x,y,d-1); } printf("%d\n",ans); return 0; }

上一篇:20140218记录
下一篇:数据库技巧

相关文章

相关评论