题解 P4151 【[WC2011]最大XOR和路径】

Mr_Wu · 2019-12-17 14:47:55 · 题解

可能是其他人太强了认为这是显然的或者我太弱了，我并没有看到明确的解释为什么正确做法对环套环的处理方案是正确的。。

先讲一下这题的正确做法，首先考虑答案路径上的点的组成，一定是 1 到 n 的一条路径（称为“主路径”）与很多简单环组成。这是因为我们从主路径走到一个环上的路径会被恰好走两次，抵消掉。

而又可以证明主路径能随便选（考虑两条主路径会构成环），所以选一个主路径，并在 dfs 树上通过返祖边找到简单环，扔进线性基就可以了。

但是可能会出现这样的问题：

可以看出来这个图可以有好几种不同的 dfs 树，在图中第一个 dfs 树能找到环 \{2,3,4\} 和 \{1,2,3,4\}，而第二个 dfs 树却只能找到 \{2,3,4\} 和 \{1,2,4\}。所以当我们计算的时候会漏掉一个简单环。让人惊讶的是，这两种 dfs 方式能得出相同的答案。

事实上，我们可以发现（这里用边集代替上面的点集） \{(1,2),(2,3),(3,4),(4,1)\} 与 \{(2,3),(3,4),(4,2)\} 进行“异或”能直接得到 \{(1,2),(4,2),(4,1)\}，因此我们猜想我们的算法找到的简单环能够通过异或操作得到所有的简单环。

证明的话可以考虑为什么线性基可以成为它所在线性空间的一组基底，大概就能证明这件事情。

用这种性质做的题也有 CF19E Fairy，建议去看看。