题解：CF2249F Even Simple Path

aaron0919 · 2026-08-07 16:08:01 · 题解

考虑直接 bfs，由于是简单路径不能走重点，如果直接记录奇偶性跑可能会在奇环上绕一圈导致爆炸。

因此记录走过哪些点，考虑 Beam Search。

对于每个点和奇偶性，我们记录 K 个不同的到达此状态走过的点的集合，这个可以压进 Bitset，K 是提前指定的一个数。

观察发现 K 取 5 可以拿到最短解和第六快（截至至 8.7）。

注意不要走到 (n,1)。可能会被 hack，可以自行调大 K。

以上是乱搞做法，甚至可以 SA 过，说不定正确率更高。

正解很简单，直接建图。

对于每个点 i 拆成 A_i,B_i 两个点并且中间连边，对于边 u,v 就连接 (A_u,A_v),(B_u,B_v)。

前一类边赋权 +\infin，后一类赋权 +\infin-1，同时把 B_1,A_N 两点删掉，如果存在完美匹配则容易发现一定是最短的偶数长度路径。

证明略，反正我不会一般图的带权完美匹配。