又见关系并查集 以POJ 1182 食物链为例

简单的关系并查集一般很容易根据给出的关系搞出一个有向的环,那么两者之间的关系就变成了两者之间的距离。

对于此题:

若u,v不在一个集合内,则显然此条语句会合法(暂且忽略后两条,下同)。

那么将fu 变为 fv的儿子时需加一条权值为 w 的边,w 满足(w + ru)%3 = (rv+ (D == 1? 0 : 1))%3(ru,rv分别为u,v与fv的关系,即距离)。

之所以在D == 2时加 1,是因为u吃v表明着u到fv的距离比v到fv的距离大1。

同理,D == 1时,表明两者到fv的距离应该相等。

若u,v在一个集合内,只需要判断ru%3 == (rv+(D == 1?):1))%3 是否成立即可。

不过这个题数据略坑啊,写成多组输入的根本过不了。

#include #include #include #include #include #include #include #include #include #pragma comment(linker, "/STACK:1024000000"); #define EPS (1e-8) #define LL long long #define ULL unsigned long long #define _LL __int64 #define INF 0x3f3f3f3f using namespace std; struct N { int fa,re; } st[50010]; int Find(int x,int &R) { int f,re = 0; f = x; while(f != st[f].fa) { re = (re+st[f].re)%3; f = st[f].fa; } R = re; int tre = 0,temp,tf; while(x != st[x].fa) { tf = st[x].fa; temp = st[x].re; st[x].re = (re-tre+3)%3; tre = (tre+temp)%3; st[x].fa = f; x = tf; } return f; } bool Merge(int w,int u,int v) { int ru,rv; int fu = Find(u,ru); int fv = Find(v,rv); if(fu != fv) { st[fu].fa = fv; if(w == 2) st[fu].re = ((rv+1)%3 - ru + 3)%3; else st[fu].re = (rv%3- ru + 3)%3; } else { if(w == 1 && ru != rv) return false; if(w == 2 && ru != (rv+1)%3 ) return false; } return true; } int main() { int n,k; int i,j,u,v,w; scanf("%d %d",&n,&k); { for(i = 1; i n || v > n || (w == 2 && u == v)) { ans++; continue; } if(Merge(w,u,v) == false) { ans++; } } printf("%d\n",ans); } return 0; }

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:HDU - 4902 Nice boat
下一篇:poj3436 ACM Computer Factory, 最大流,输出路径
相关文章

poj 1182 食物链(经典!种类并查集)

POJ 1182 食物链 并查集

[ACM] poj 1182 食物链(并查集)

poj 1182 食物链 (种类并查集)

POJ1182 食物链 [并查集变种]

POJ 1182 食物链[并查集]

POJ 1182 :食物链(并查集)

POJ 1182 食物链

POJ 1182 食物链(种类并查集)

POJ 1182 食物链 (种类并查集)

图文推荐
又见关系并查集 以POJ 1182 食物链为例
ZOJ 3640 Help Me
又见关系并查集 以POJ 1182 食物链为例
CF 518C(Anya and
又见关系并查集 以POJ 1182 食物链为例
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2013-07-03 人气:0
本文关键词:
分享到:

相关文章

  • POJ 1182 :食物链(并查集) 2012-03-23

    食物链 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 43526 Accepted: 12679 Description 动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B, B吃C,C吃A。 现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。 有人用两种说法对这N个动物所构成的食物链关系进行描述: 第一种说法是"1 X Y",表示X和Y是同类。 第二种说法是

  • POJ 1182 食物链 (种类并查集) 2015-01-02

    食物链 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 47729 Accepted: 13895 Description 动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B, B吃C,C吃A。 现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。 有人用两种说法对这N个动物所构成的食物链关系进行描述: 第一种说法是"1 X Y",表示X和Y是同类。 第二种说法是

  • POJ 1988 Cube Stacking (种类并查集) 2013-02-28

    题目地址:POJ 1988 这道题的查找合并的方法都能想的到,就是一点没想到,我一直天真的以为查询的时候,输入后能马上输出,这样的话在合并的时候就要所有的结点值都要算出来,但是经过路径压缩之后,没办法全部都处理到,如果不压缩妥妥的TLE。。于是看了看网上的题解。才发现自己是多么的天真(ben,四声)。。在查询的时候只要找一次跟就可以了。。这样不需查询的也就没必要处理出来。反而更省时。 这题的基本思路是很好想的。另开两个数组,一个记录以此节点为根的子节点的数目(这样合并的时候只需要加另一个根的数目

  • POJ 1703 Find them, Catch them(种类并查集) 2013-07-06

    题目地址:POJ 1703 种类并查集水题。 代码如下: #include #include #include #include #include #include #include #include #include #include #include using namespace std; int bin[600000], rank[600000]; int find1(int x) { int y; if(bin[x]!=x) { y=bin[x]; bin[x]=find1(bin[x

  • POI导出EXCEL经典实现 2012-01-04

    1.Apache POI简介 Apache POI是Apache软件基金会的开放源码函式库,POI提供API给Java程式对Microsoft Office格式档案读和写的功能。 .NET的开发人员则可以利用NPOI (POI for .NET) 来存取 POI 的功能。 2.POI结构 HSSF - 提供读写Microsoft Excel XLS格式档案的功能。 XSSF - 提供读写Microsoft Excel OOXML XLSX格式档案的功能。 HWPF - 提供读写Microsoft

  • UVA之11462 - Age Sort 2012-11-05

    【题目】 You are given the ages (in years) of all people of a country with at least 1 year of age. You know that no individual in that country lives for 100 or more years. Now, you are given a very simple task of sorting all the ages in ascending order.

  • 杭电1279 Stone Game(经典博弈) 2012-11-15

    Stone Game Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 2539 Accepted Submission(s): 741 Problem Description This game is a two-player game and is played as follows: 1. There are n boxes; each

  • poj3311 经典tsp问题 2013-01-06

    题目的大概意思就是一个人到一些城市送披萨,要求找到一条路径能够遍历每一个城市后返回出发点,并且路径距离最短。最后输出最短距离即可。注意:每一个城市可重复访问多次。 由于题中明确说了两个城市间的直接可达路径(即不经过其它城市结点)不一定是最短路径,所以需要借助邻接矩阵首先求出任意两个城市间的最短距离。这一步骤使用Floyd最短路径算法即可。然后,在此基础上来求出遍历各个城市后回到出发点的最短路径的距离,即求解TSP问题。 TSP问题目前有多种解法:搜索解法,动归解法,启发式解法。这里就针对poj

  • C++ Primer----智能指针类 2 2013-02-08

    指针带给了 C++巨大的灵活性,然而同样也带来无数的问题,悬挂指针,内存泄漏等。 int *pInt = new int(1); // Do not forget delete pInt; 智能指针就是一种能够有效避免悬挂指针的方法。通过一个类,来管理指针的复制, delete 等。从而使用户可以放心地使用指针。 一种智能指针的实现方法是,通过一个计数,追踪当前指向同一块地址的指针有多少个, 当没有指针指向这块地址的时候,自动释放资源。从而有效地避免了 内存泄漏 和 悬挂指针问题。 // Las

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.053 (s). 10 q(s)