QOJ.ac

QOJ

Type: Editorial

Status: Open

Posted by: Milmon

Posted at: 2026-04-01 21:37:58

Last updated: 2026-04-01 21:38:05

Back to Problem

题解

模拟 Boruvka 的过程,每一轮每个点向所有点发送当前连通块连出去边权最小值以及连接的点编号和当前所在的连通块编号,正好是 $48 + 8 + 8 = 64$ 位。而对于权值和的计算,由于自己下一轮可以重新计算这一轮的最小边信息,所以不需要向自己发送最小边,于是改为给自己发送当前答案和当前所在的连通块编号,正好是 $56 + 8 = 64$ 位。总轮数为 $\lfloor \log_2 N \rfloor + 1 = 9$ 轮。

考虑优化最后几轮,当连通块删减为 $16$ 个时,改用另一种策略:求出两两连通块之间的最小边权,然后暴力计算答案。具体地,将 $\binom{16}{2}$ 个连通块对每个都分配给一个点,第一轮每个点都向对应点发送自己到目标连通块的边权最小值,这样每个被分配的点就可以计算出最小边权,再用第二轮把信息汇总到同一个结点处,即可计算出答案。这样的算法需要 $7$ 轮。

最后注意到前四轮中,每个点都需要发送边权信息的原因是不确定这条边是否会被统计到答案中。但是对于第一轮,每个点作为单独的连通块,最小的边一定会被计入答案。所以第一轮中可以传输两条边,具体需要发送最小边的目标点和次小边的边权和目标点,共 $48 + 8 + 8 = 64$ 位。此时经过三轮后连通块数变为 $256 \to 85 \to 42 \to 21$,$\binom{21}{2} = 210$ 个点能够完成分配,总共只需要 $6$ 轮,可以通过此题。

Comments

No comments yet.