SNOI 2019 积木

· · 题解

拜谢 JCY_std。

考虑这样刻画问题：给原图黑白染色，得到一个二分图，相当于给出了原图的两个最大匹配，要求走一条交错路把一个变成另一个。求一下两张图的对称差，它的结构形如一条连接两个未匹配点的链，加上一堆环。首先把链走了，那么剩下的就是一堆环。考虑将匹配的点彼此缩起来后建立一个 DFS 树，沿着这个 DFS 树走，当遇到某个在环上的点时，立刻沿着这个环转一圈以后回到原来的点，由于这是第一个遇到的这个环上的点，所以先前在 DFS 树上走的路径不会影响这个环的形状，所以一定可以这样走。走完一圈以后，你发现除了这个环消失了以外，其他信息都没有受影响，所以你正常走 DFS 树，走完一棵子树就回溯。最后所有可达的环都被转了一圈消失了，而其他边刚好在进入子树和出子树时被反转一次，状态不变，这样就解决了这个问题。所有位置显然都是可达的，因为任意两个骨牌有公共边接触就会有非匹配边相连。