BZOJ 1854: [Scoi2010]游戏 (并查集)

Description

lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示。当他使用某种装备时,他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。 游戏进行到最后,lxhgww遇到了终极boss,这个终极boss很奇怪,攻击他的装备所使用的属性值必须从1开始连续递增地攻击,才能对boss产生伤害。也就是说一开始的时候,lxhgww只能使用某个属性值为1的装备攻击boss,然后只能使用某个属性值为2的装备攻击boss,然后只能使用某个属性值为3的装备攻击boss……以此类推。 现在lxhgww想知道他最多能连续攻击boss多少次?

Input

输入的第一行是一个整数N,表示lxhgww拥有N种装备 接下来N行,是对这N种装备的描述,每行2个数字,表示第i种装备的2个属性值

Output

输出一行,包括1个数字,表示lxhgww最多能连续攻击的次数。

Sample Input

3
1 2
3 2
4 5

Sample Output

2

HINT

【数据范围】
对于30%的数据,保证N < =1000
对于100%的数据,保证N < =1000000

Source

 

 

思路:

看到了二分图匹配的题解,但是感觉很错啊?

正确的做法是,将武器看成边,将每个武器的2种属性看成点。

使用某种属性,就要消耗一条边。

因此如果一个联通快是树形结构,k个点,k-1条边,因此有一个属性无法被使用。

由于要求是从1开始递增得攻击,因此显然使得属性最大的点不被使用是最优的。

如果一个联通块有环,那么所有的树型都可以被使用。

注意这个联通快有无环影响计数的思维,和codeforces # 440 div2 E. Points, Lines and Ready-made Titles  很像

 

poj 3310 Caterpillar (树的直径+并查集判环+dfs判断连通性)

poj3310 题目链接

题意:给出一个无向图。。。问是否满足。。联通,并且无环,并且能找到一条路径,图中所有的顶点要么在这条路径上,要么与这条路径上的顶点相邻。

思路:一个一个来。。。联通的话任意起点开始跑一遍dfs? 开一个bool数组标记走过的点。。最后扫一遍。。看是否有点没走过

环的话并查集就好。。

关键是第三个条件。。。根据题中题中的例子。。感觉如果存在这样的路径。。。那么这样的路径应该尽可能长?

于是想到求直径。。。然后在bfs的时候顺便记录路径。。。这样我就知道直径是哪些点。。。然后对于所有点。。判断是否在这条直径上或者与之相邻就好。。。

具体做法是。。。开了一个bool数组ok标记直径上的点。。。在存边的时候用一个to[]数组表示相连。。。to[u]=v,to[v]=u…

然后只要ok[i]或者ok[to[i]]满足其一就好。。。

又是1A,蛤蛤蛤蛤蛤,我好神啊(误

 

 

 

 

hdu 4514 湫湫系列故事——设计风景线 (无向图并查集判环+非联通图的最长路径)

hdu4514

题意:给出一个无向图。。问是否有环。。。有的话输出YES。。如果没有环的话。。输出最长路径。。

思路:无向图判环并查集就好。。。关于最长路径这里。。一开始以为就是树的直径。。。

但是需要注意的是。。。题目并没有保证图一定是联通的。。。所以gg了。。

也就是要在一个不联通的图中求最长路径。。。

没想出来。。搜了一下。。有树形dp的做法。。。有并查集的时候带权的做法。。。

不过感觉最容易想到的还是求多次直径的做法。。。

也就是。。每一个联通块求一次直径。。。取最大。。。

具体做的时候。。。加一个bool数组在bfs标记一下就好。。。

以及bfs的时候。。。由于我之后是要得到最大值。。。而图本身可能是不联通的。。所以要注意d数组初始化的问题。。。不能初始化成0x3f…(这么说来即使联通也没必要初始化成0x3f。。。。)

还有一点,这道题数据量比较大。。。用vector存图会MLE …

 

 

 

 

 

hdu 2874 Connections between cities (添加虚点,并查集+LCA(rmq+dfs))

hdu2874题目链接

题意:给一个森林,问两点的最短距离,或者输出两点不联通。

思路:最最重要的一点是:添加虚点!

最最重要的一点是:添加虚点!

最最重要的一点是:添加虚点!

所谓虚点,就是之前假设某个不存在的点,有点类似做辅助线。

通过添加虚点,我们可以把这个森林转化成一棵树。

这样求两点的距离就可以转化成一棵树上的两点的距离。

用dis[u]+dis[v]-2*dis[LCA(u,v)]来求。 dis[i]表示节点i到新的树根节点的距离。

不联通的话就是LCA 为0的情况(0是添加的虚点,作为新的树的根)

具体添加虚点的方法是:森林中每棵树的根连边到虚点上。权值大小随意,因为最后会抵消(?) 为了知道每棵树的根,需要用到并查集(其实根是随便定义的,但是森林中每棵树只能一个点和虚点相连不然就出现环了,所以需要用到并查集)

以及了解了(?)并查集的非递归的路径压缩写法。。。?

缺点是速度更慢,优点是不会爆栈。。。

还有需要学习一下按rank合并和按size合并的进阶并查集。。。?

以及:RE了好多次是因为。。。添加了虚点0,所以各种下标都应该是从0开始,初始化清空的时候忘了(从0开始)清vector…导致多组数据一直往edge[0]里面添加边。。。然后就炸了(手动微笑)

 

 

 

 

bc #77 ||hdu 5652 India and China Origins (图的动态连通性问题,并查集or 二分+bfs验证连通性)

题目链接
题意:没图不好描述,有中文题面中文题面,直接看吧。
思路:据说这道题有三种做法。 当时比赛一种都不会。

先说一种:做法是把格子看成点,可以到达的相邻格子之间看成有边相连,然后倒过来用并查集判断无向图的连通性。具体做法是:先统计初始所有空的位置,然后把所有要增加的山都加上(先统计空的位置是因为山之后要去掉,而去掉以后要得到该点的标号),然后将把所有空的点以及china(设标号为n*m+1)点,和india(设标号为n*m+2) 点通过并查集来合并..可以从上往下从左往右,每次只需要判断上面的点和左边的点是否有空,如果有就用并查集合并。 china点和india点特殊搞就好。

然后判断india和china是否联通,如果是则输出-1.否则从最后添加的山开始移除,每次移除一座山,添加四个方向能添加的边(注意这里不要忘记如果改点在第0行或者第n-1行还要添加和china或者india的边)

然后移除后询问india和china是否联通 (root(china)==root(india)?)

如果时间i联通了,而i+1没有联通,说明时间i是两国最早的失去联系的时间。

 

第一次做这种题目,这种题目的一般做法都是倒过来做。貌似还有一个二分删除的山+bfs判断连通性的。。。? 窝再搞搞看。
update :二分+bfs判断连通性。其实这个思路更常规。。做法就是字面意思。注意无解的判断即可。

 

并查集解法:

 

 

二分+bfs判断连通性。

bc #73 B || hdu 5631 Rikka with Graph (并查集判断无向图的连通性)

http://acm.hdu.edu.cn/showproblem.php?pid=5631
题意;给出一张n个点n+1(n<=100)条边的无向图,现在删除若干条边(至少一条边),问删完之后图依然联通的方案数。
思路:分析可知,由于只删边,不删点,n个点,最少需要n-1条边才能联通,所以最多删两条边。我们可以暴力枚举删除的两条边(或者一条边) O(n^2)的复杂度完全可以接受。剩下的问题就变成了每次删边之后判断图的连通性。 题解给出的是bfs。。。大概是bfs一遍,然后入队的点数是n就联通? 或者dfs一遍也可以? 也是标记过的点数是n就说明联通? 但是看到排名考前的人都是用到了并查集来判断…比较巧妙。

具体做法是:先把所有的点孤立出来,然后开始添加边,每次union成功(就是添加了一条边)的时候计数器+1,n个点如果能合并n-1次,也就是添加了n-1条有效边(最多也只可能是n-1条,那么说明这n个点之间是联通的。

第一次这样用并查集…憋说话,用心感悟。

 

 

bzoj 1604: [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居 (曼哈顿距离的转化【拆点】+set+并查集)

http://www.lydsy.com/JudgeOnline/problem.php?id=1604
题意:了解奶牛们的人都知道,奶牛喜欢成群结队.观察约翰的N(1≤N≤100000)只奶牛,你会发现她们已经结成了几个“群”.每只奶牛在吃草的时候有一个独一无二的位置坐标Xi,Yi(l≤Xi,Yi≤[1..10^9];Xi,Yi∈整数.当满足下列两个条件之一,两只奶牛i和j是属于同一个群的:
1.两只奶牛的曼哈顿距离不超过C(1≤C≤10^9),即lXi – xil+IYi – Yil≤C.
2.两只奶牛有共同的邻居.即,存在一只奶牛k,使i与k,j与k均同属一个群.
给出奶牛们的位置,请计算草原上有多少个牛群,以及最大的牛群里有多少奶牛

思路:一开始并没有什么思路…入手点是关于曼哈顿距离的转化。

先看曼哈顿距离的定义

|x1x2|+|y1y2|

拆绝对值

x1x2+y1y2x1x2+y2y1

x2x1+y1y2x2x1+y2y1

|x1+y1(x2+y2)||x1y1(x2y2)|

x1+y1xx1y1y

|x1x2||y1y2|

所以原要求1转化为

max(|x1x2|,|y1y2|)<=c

引用自:http://blog.csdn.net/wzq_QwQ/article/details/47746091

 

这样就有思路了。如果两个点属于同一个群,那么必须这两个点的x的差在c范围内,并且两个点的y的差也在范围内。 我们可以先按照一个 坐标排序,不妨以x为关键字排序,然后维护一段点的序列,使得这段序列中的所有的点的横坐标(其实就是最大减去最小)的差都在c范围内。然后对于序列中的所有点,我们想要知道有没有群“接纳”最新加入的点,二分找到比当前新加入点的纵坐标大的最小值和比当前新加入点的纵坐标小的最大值(set的lower_bound 第一次用),判断是否满足纵坐标的差在c的范围内。如果是,则用并差集合合并一下。

用multiset的原因是经过变换后点的坐标可能重复,以及multiset删除元素的时候不能直接删,因为会把所有相同的值删掉。

 

重要的话再说一遍:这道题最关键也是最大的收货就是,关于曼哈顿距离的变换。

 

 

poj 2492 A Bug’s Life (并查集)

http://poj.org/problem?id=2492

Hint

Huge input,scanf is recommended.
也是带种类的冰茶几。
由于只分了两类…我们还是可以按照上道题的做法。。
感觉完全是一样的题啊。。
结果一直WA。。。。
最后发现。。。我边读入边判断。。发现同性恋了就直接Break掉了。。。后面改组的数据读到下一组去了233,不WA就日了汪了。。。
还是把数据的读完再进行操作比较好==

poj 1703 Find them, Catch them (并查集)

http://poj.org/problem?id=1703
种类冰茶几…看到还有一种算是拓展的交加权冰茶几?
看到有做法是在开一个数组。。。记录是哪一组….
但是因为只有两组….我们可以分别存…
因为不知道每一个D的两个人分别是哪个组(帮派?)
可以都存一下。
TLE了两次….应该是用了cin的事。。。改成scanf就变WA了。。。
想了下。原来是我对“not sure yet”的判断出现失误。
我开了一个v数组,记录在D下出现的人。
我误以为出现的人的帮派一定是确定的。
实际上并不是。
比如 1,3 5,7 3和7都出现了。但是3和7是一组与否显然还是“not sure yet”