并查集 - Page 3

「CF437D」The Child and Zoo
Ofcourseourchildlikeswalkinginazoo.Thezoohas n areas,thatarenumberedfrom 1 to n.The i-thareacontains ai animalsinit.Alsothereare m roadsinthezoo,andeachroadconnectstwodistinctareas.Naturallythezooisconnected,soyoucanreachanyareaofthezoofromanyotherareausingtheroads.Ourchildisverysmart.Imaginethechildwanttogofromarea p toarea q.Firstlyheconsidersallthesimpleroutesfrom p to q...
42014年6月1日3,714并查集

「JoyOI1863」[Poetize I] 黑魔法师之门
背景Background经过了16个工作日的紧张忙碌，未来的人类终于收集到了足够的能源。然而在与Violet星球的战争中，由于Z副官的愚蠢，地球的领袖applepi被邪恶的黑魔法师Vani囚禁在了Violet星球。为了重启Nescafé这一宏伟的科技工程，人类派出了一支由XLk、Poet_shy和lydrainbowcat三人组成的精英队伍，穿越时空隧道，去往Violet星球拯救领袖applepi。描述Descriptionapplepi被囚禁的地点只有一扇门，当地人称它为“黑魔法...
52014年5月23日3,952并查集
「BZOJ1529」[POI2005] ska Piggy banks
DescriptionByteazar有N个小猪存钱罐.每个存钱罐只能用钥匙打开或者砸开.Byteazar已经把每个存钱罐的钥匙放到了某些存钱罐里.Byteazar现在想买一台汽车于是要把所有的钱都取出来.他想尽量少的打破存钱罐取出所有的钱,问最少要打破多少个存钱罐.Input第一行一个整数N(1<=N<=1.000.000)–表示存钱罐的总数.接下来每行一个整数,第i+1行的整数代表第i个存钱罐的钥匙放置的存钱罐编号.Output一个整数表示最少打破多少个存...
02014年5月17日4,774并查集,图的连通
「BZOJ1116」[POI2008] CLO
DescriptionByteotia城市有n个townsm条双向roads.每条road连接两个不同的towns,没有重复的road.你要把其中一些road变成单向边使得：每个town都有且只有一个入度Input第一行输入nm.1<=n<=100000,1<=m<=200000下面M行用于描述M条边.OutputTAK或者NIE常做POI的同学,应该知道这两个单词的了...SampleInput451223133414SampleOutputTAK上图给出了一种连接方式.题解这题令我突然想到了scoi游戏首先我们...
02014年5月13日4,626并查集
「BZOJ1854」[SCOI2010] 游戏
Descriptionlxhgww最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有2个属性，这些属性的值用[1,10000]之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。游戏进行到最后，lxhgww遇到了终极boss，这个终极boss很奇怪，攻击他的装备所使用的属性值必须从1开始连续递增地攻击，才能对boss产生伤害。也就是说一开始的时候，lxhgww只能使用某个属性值为1的装备攻击boss，...
82014年5月8日8,941并查集
「JoyOI1460」旅行
描述DescriptionA国有n座城市，每座城市都十分美，这使得A国的民众们非常喜欢旅行。然而，A国的交通十分落后，这里只有m条双向的道路，并且这些道路都十分崎岖，有的甚至还是山路，只能靠步行。通过每条道路的长度、泥泞程度等因素，我们给每条道路评估一个“崎岖度”，表示通过这条道路的不舒适程度。从X城市经过若干条道路到达Y城市，我们称这次旅行的“代价”为所经过道路“崎岖度”的最大值。当然，如果从X城市到Y城市...
112014年3月20日4,609并查集,二分法
「POJ2588」Snakes
DescriptionBuffaloBillwishestocrossa1000x1000squarefield.Anumberofsnakesareonthefieldatvariouspositions,andeachsnakecanstrikeaparticulardistanceinanydirection.CanBillmakethetripwithoutbeingbitten?InputAssumethatthesouthwestcornerofthefieldisat(0,0)andthenorthwestcornerat(0,1000).Theinputconsistsofalinecontainingn<=1000,thenumberofsnakes.Alinefollowsforeachsnake,containingthreerealnumb...
02014年3月19日3,073并查集
「BZOJ1015」[JSOI2008] 星球大战starwar
Description很久以前，在一个遥远的星系，一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天，凭着一个偶然的机遇，一支反抗军摧毁了帝国的超级武器，并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。但好景不长，很快帝国又重新造出了他的超级武器。凭借这超级武器的力量，帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁，两个星球之间的通讯通道也开始不可靠起来。现在，反...
32014年2月23日7,374并查集,离线处理
「hdu1272」小希的迷宫
Description上次Gardon的迷宫城堡小希玩了很久（见ProblemB），现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样，首先她认为所有的通道都应该是双向连通的，就是说如果有一个通道连通了房间A和B，那么既可以通过它从房间A走到房间B，也可以通过它从房间B走到房间A，为了提高难度，小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图...
02014年2月5日4,181并查集
「BZOJ1202」[HNOI2005] 狡猾的商人
Description刁姹接到一个任务，为税务部门调查一位商人的账本，看看账本是不是伪造的。账本上记录了n个月以来的收入情况，其中第i个月的收入额为Ai(i=1,2,3...n-1,n)，。当Ai大于0时表示这个月盈利Ai元，当Ai小于0时表示这个月亏损Ai元。所谓一段时间内的总收入，就是这段时间内每个月的收入额的总和。刁姹的任务是秘密进行的，为了调查商人的账本，她只好跑到商人那里打工。她趁商人不在时去偷看账本，可是她无法将账本偷出...
02014年1月7日6,382并查集
并查集学习总结
在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受，只能采用一种全新的抽象的特殊数据结构——并查集来描述。初始化把每个点所在集合初始化为其自身。father[i]=i;通常来说，这个步骤在每次使用该数据结...
02014年1月7日5,006并查集
「vijos1022」Victoria的舞会2
描述Victoria是一位颇有成就的艺术家，他因油画作品《我爱北京天安门》闻名于世界。现在，他为了报答帮助他的同行们，准备开一个舞会。Victoria准备邀请n个已经确定的人，可是问题来了：这n个人每一个人都有一个小花名册，名册里面写着他所愿意交流的人的名字。比如说在A的人名单里写了B，那么表示A愿意与B交流；但是B的名单里不见的有A，也就是说B不见的想与A交流。但是如果A愿意与B交流，B愿意与C交流，那么A一定...
52013年12月31日3,722深度搜索,并查集