mengbierr

一个蒟蒻的博客

3月07

Codeforces 845G Shortest Path Problem?

题目大意

求1到n的最短异或路径。

题解

先找到一条从1到n的路径,然后求一个生成树,其余的边都会与别的边形成环,这些环互相异或能组合出所有环。

我们发现可以任意的异或一个任意位置的环,因为从一个点走到环上一点,绕一圈后延原路返回。

这样我们就可以用线性基求出异或出的最小数了。

 

发表评论

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