bzoj 2959 长跑 题解

Description

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

Solution

开2个并查集,一个保存的是原树之间的关系用来判断连通性,一个保存的是强联通分量的代表节点。

每连一条边u-v,就用第一个并查集判断一下u,v是否连通。如果没有,就直接连接,否则意味着图中出现了一个环。我们把这个环上的所有节点(也就是原来u-v的路径上的所有点)的点权移到一个代表节点上,然后丢掉其他所有点,还要把所有点的第二个并查集的父亲赋值为代表节点,因为它们属于的强联同分量改变了。

对于舍弃掉的点,只要保证不会在各种操作的时候跳到即可。具体实现时,只要把所有的fa改为getfa(fa)即可,就会跳到代表节点上。

Code

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇