bzoj 4070 [Apio2015]雅加达的摩天楼

Posted by

题目链接

https://www.lydsy.com/JudgeOnline/problem.php?id=4070

题解

要是直接建图的话在极端条件下会有\(n^2\)条边,不考虑;

发现对于两个doge \(i,j\),如果\(p_i=p_j\)并且\(b_i mod p_i=b_j mod p_j\),他们可以跳到的点是相同的,不用重复构图;

考虑根号平衡,额外建立\(\sqrt n\)层图,第\(i\)层中每条边连接的两个点之间相距\(i\),权值为\(1\),每个点与原图中对应的点连接,权值为\(0\);

对于\(p<\sqrt n\)的doge,将原图中\(b\)节点与第\(p\)层的\(b\)节点连接,权值为\(0\);

对于剩下的doge,直接在原图中以\(b\)为起点向各个能跳到的点连边(不会超过\(\sqrt n\)条边);

注意把空间开够,如果\(n\)足够小就不分层了。

代码

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注