Tag: 并查集

5 篇文章

bzoj 2959 长跑 题解
Description   某校开展了同学们喜闻乐见的阳光长跑活动。为了能“为祖国健康工作五十年”,同学们纷纷离开寝室,离开教室,离开实验室,到操场参加3000米长跑运动。一时间操场上熙熙攘攘,摩肩接踵,盛况空前。  为了让同学们更好地监督自己,学校推行了刷卡机制。  学校中有n个地点,用1到n的整数表示,每个地点设有若干个刷卡机。  有以下三类事…
Luogu P4255 公主の#18文明游戏 题解
Describe 题目链接 这个游戏里有n个城市,标号1~n,有m条双向道路相连,编号1~m。 游戏里会系统会添加Ni个人到一个城市Xi,并给定这些人的信仰Ci 系统还会切断一条道路,并给定道路编号Xi 系统还会给定一个城市Xi,询问从Xi出发可以到达的所有城市中选择Ni个人,使得他们信仰都为Ci的概率为多少,对19260817取模。 Soluti…
Luogu P3535 [POI2012]TOU-Tour de Byteotia 题解
Link 题意 给定一个$n$个点$m$条边的无向图,问最少删掉多少条边能使得编号小于等于$k$的点都不在环上。 思路 要想让编号小于等于$k$的点都不在环上,那么就最好让所有编号大于$k$的边都在环上。 那么可以用并查集把所有编号大于$k$的边连起来,再判断编号小于等于$k$的边是否在环上即可。 Code [crayon-5fbcdb56b550…