P8281

w33z8kqrqk8zzzx33 · 2023-04-28 20:14:33 · 题解

本题非 DLX 做法时间复杂度可以证明。

将 dfs 搜索空间抽象为一棵树，节点个数 n!，深度 n。每一个节点对应原图中固定回路。如果对于任何节点可以 O(T(n,m)) 判断子树内是否有解，可以 O(T(n,m)Kn^2) 找出所有回路。

确定子树内是否有解就是钦定某些点在最终回路中的出边，判断可否完成回路。通过 deletion-contraction 删掉不可能选的边，缩掉钦定选的边，将问题转化成判断 D-C 后的图是否存在回路。

判断回路是否存在可以用一些启发式，比如调整法，最后时间复杂度 O(Kn^4)。当然用更弱得出可能有解而不是肯定有解也可以剪掉足够多的节点，这样的时间复杂度相对难证。