[BZOJ2959]长跑(LCT,并查集)

发布于 2018-01-22  168 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2959]长跑(LCT,并查集)

Description

某校开展了同学们喜闻乐见的阳光长跑活动。为了能“为祖国健康工作五十年”,同学们纷纷离开寝室,离开教室,离开实验室,到操场参加3000米长跑运动。一时间操场上熙熙攘攘,摩肩接踵,盛况空前。
  为了让同学们更好地监督自己,学校推行了刷卡机制。
  学校中有n个地点,用1到n的整数表示,每个地点设有若干个刷卡机。
  有以下三类事件:
  1、修建了一条连接A地点和B地点的跑道。
  2、A点的刷卡机台数变为了B。
  3、进行了一次长跑。问一个同学从A出发,最后到达B最多可以刷卡多少次。具体的要求如下:
  当同学到达一个地点时,他可以在这里的每一台刷卡机上都刷卡。但每台刷卡机只能刷卡一次,即使多次到达同一地点也不能多次刷卡。
  为了安全起见,每条跑道都需要设定一个方向,这条跑道只能按照这个方向单向通行。最多的刷卡次数即为在任意设定跑道方向,按照任意路径从A地点到B地点能刷卡的最多次数。

Http

BZOJ

Tag

LCT,并查集

解决思路

算是这题的强化板。
先看题目中关于单向方向的设置,讲得那么复杂,其实就是要求不能走一条边再反向返回,那么说白了就是从\(u\)到\(v\)的话可以走环和直接路径,不能走到一棵子树中去再原路返回。
看到环一定是可以走的,所以我们可以把环缩成一个点,那么就直接动态求两点之间的路径点权和即可。
综上,并查集维护缩点,\(LCT\)维护动态路径点权和。
需要注意的是,第二个操作是修改某一个点上的机器数量,而我们缩点后并没有统计单个点的贡献,所以要在另外存一下原来每一个点的机器数,方便修改。
最后就是与这题一样需要注意,因为我们缩了点,所以在\(LCT\)中每一步都要\(find\)一下缩点后的编号

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ2959]长跑(LCT,并查集)


HNCJ OIer