• 「BZOJ1116」[POI2008] CLO

    「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日2,902并查集
  • 「BZOJ1854」[SCOI2010] 游戏

    「BZOJ1854」[SCOI2010] 游戏

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

    102014年5月8日6,502并查集
  • 「JoyOI1460」旅行

    「JoyOI1460」旅行

    描述DescriptionA国有n座城市,每座城市都十分美,这使得A国的民众们非常喜欢旅行。然而,A国的交通十分落后,这里只有m条双向的道路,并且这些道路都十分崎岖,有的甚至还是山路,只能靠步行。通过每条道路的长度、泥泞程度等因素,我们给每条道路评估一个“崎岖度”,表示通过这条道路的不舒适程度。从X城市经过若干条道路到达Y城市,我们称这次旅行的“代价”为所经过道路“崎岖度”的最大值。当然,如果从X城市到Y城市...

    112014年3月20日2,858并查集,二分法
  • 「POJ2588」Snakes

    「POJ2588」Snakes

    DescriptionBuffaloBillwishestocrossa1000x1000squarefield.Anumberofsnakesareonthefieldatvariouspositions,andeachsnakecanstrikeaparticulardistanceinanydirection.CanBillmakethetripwithoutbeingbitten?InputAssumethatthesouthwestcornerofthefieldisat(0,0)andthenorthwestcornerat(0,1000).Theinputconsistsofalinecontainingn<=1000,thenumberofsnakes.Alinefollowsforeachsnake,containingthreerealnumb...

    02014年3月19日1,462并查集
  • 「BZOJ1015」[JSOI2008] 星球大战starwar

    「BZOJ1015」[JSOI2008] 星球大战starwar

    Description很久以前,在一个遥远的星系,一个黑暗的帝国靠着它的超级武器统治者整个星系。某一天,凭着一个偶然的机遇,一支反抗军摧毁了帝国的超级武器,并攻下了星系中几乎所有的星球。这些星球通过特殊的以太隧道互相直接或间接地连接。但好景不长,很快帝国又重新造出了他的超级武器。凭借这超级武器的力量,帝国开始有计划地摧毁反抗军占领的星球。由于星球的不断被摧毁,两个星球之间的通讯通道也开始不可靠起来。现在,反...

    42014年2月23日5,473并查集,离线处理
  • 「hdu1272」小希的迷宫

    「hdu1272」小希的迷宫

    Description上次Gardon的迷宫城堡小希玩了很久(见ProblemB),现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样,首先她认为所有的通道都应该是双向连通的,就是说如果有一个通道连通了房间A和B,那么既可以通过它从房间A走到房间B,也可以通过它从房间B走到房间A,为了提高难度,小希希望任意两个房间有且仅有一条路径可以相通(除非走了回头路)。小希现在把她的设计图给你,让你帮忙判断她的设计图...

    02014年2月5日2,490并查集
  • 「BZOJ1202」[HNOI2005] 狡猾的商人

    「BZOJ1202」[HNOI2005] 狡猾的商人

    Description刁姹接到一个任务,为税务部门调查一位商人的账本,看看账本是不是伪造的。账本上记录了n个月以来的收入情况,其中第i个月的收入额为Ai(i=1,2,3...n-1,n),。当Ai大于0时表示这个月盈利Ai元,当Ai小于0时表示这个月亏损Ai元。所谓一段时间内的总收入,就是这段时间内每个月的收入额的总和。刁姹的任务是秘密进行的,为了调查商人的账本,她只好跑到商人那里打工。她趁商人不在时去偷看账本,可是她无法将账本偷出...

    02014年1月7日4,571并查集
  • 并查集学习总结

    并查集学习总结

    在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。这一类问题数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受,只能采用一种全新的抽象的特殊数据结构——并查集来描述。 初始化把每个点所在集合初始化为其自身。father[i]=i;通常来说,这个步骤在每次使用该数据结...

    02014年1月7日2,443并查集
  • 「vijos1022」Victoria的舞会2

    「vijos1022」Victoria的舞会2

    描述Victoria是一位颇有成就的艺术家,他因油画作品《我爱北京天安门》闻名于世界。现在,他为了报答帮助他的同行们,准备开一个舞会。Victoria准备邀请n个已经确定的人,可是问题来了:这n个人每一个人都有一个小花名册,名册里面写着他所愿意交流的人的名字。比如说在A的人名单里写了B,那么表示A愿意与B交流;但是B的名单里不见的有A,也就是说B不见的想与A交流。但是如果A愿意与B交流,B愿意与C交流,那么A一定...

    52013年12月31日1,752深度搜索,并查集
  • 「CODEVS1540」银河英雄传说

    「CODEVS1540」银河英雄传说

    描述公元五八○一年,地球居民迁移至金牛座α第二行星,在那里发表银河联邦创立宣言,同年改元为宇宙历元年,并开始向银河系深处拓展。宇宙历七九九年,银河系的两大军事集团在巴米利恩星域爆发战争。泰山压顶集团派宇宙舰队司令莱因哈特率领十万余艘战舰出征,气吞山河集团点名将杨威利组织麾下三万艘战舰迎敌。杨威利擅长排兵布阵,巧妙运用各种战术屡次以少胜多,难免恣生骄气。在这次决战中,他将巴米利恩星域战场划分成30000列...

    12013年12月27日2,872并查集
  • 「CODEVS1001」[BZOJ1050] 舒适的路线

    「CODEVS1001」[BZOJ1050] 舒适的路线

    题目描述DescriptionZ小镇是一个景色宜人的地方,吸引来自各地的观光客来此旅游观光。Z小镇附近共有N(1<N≤500)个景点(编号为1,2,3,…,N),这些景点被M(0<M≤5000)条道路连接着,所有道路都是双向的,两个景点之间可能有多条道路。也许是为了保护该地的旅游资源,Z小镇有个奇怪的规定,就是对于一条给定的公路Ri,任何在该公路上行驶的车辆速度必须为Vi。频繁的改变速度使得游客们很不舒服,因此大家从一个景...

    02013年12月21日4,809kruskal,并查集
  • 「vijos1250」最勇敢的机器人

    「vijos1250」最勇敢的机器人

    背景Wind设计了很多机器人。但是它们都认为自己是最强的,于是,一场比赛开始了~描述机器人们都想知道谁是最勇敢的,于是它们比赛搬运一些物品。它们到了一个仓库,里面有n个物品,每个物品都有一个价值Pi和重量Wi,但是有些物品放在一起会爆炸,并且爆炸具有传递性。(a和b会爆炸、b和c会爆炸则a和c会爆炸)机器人们可不想因此损失自己好不容易从Wind那里敲诈来的装备,于是它们想知道在能力范围内,它们最多可以拿多少价值的...

    02013年12月19日2,213背包动规,并查集