自动搬运

查看原文

来自洛谷，原作者为

	w33z8kqrqk8zzzx33 **

搬运于2025-08-24 22:37:37，当前版本为作者最后更新于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)$。当然用更弱得出可能有解而不是肯定有解也可以剪掉足够多的节点，这样的时间复杂度相对难证。