题目描述

有一张n个节点的无向图，对于所有 (i,j)，判断 i 和 j 之间是否存在哈密顿路径

1<=n<=24

哈密顿路径：经过每个点恰好一次

乐乐乐乐乐

考虑暴力：\(dp[i][j][st]\)表示从\(i\)开始到\(j\)的经过的点的状态\(st\)(\(st\)状压每一个点是否被经过)是否可行

转移时枚举一个\(k\)，类似Floyd,要求\(st\)的并只有\(k\)

复杂度:\(O(n^32^n)\)，轻轻松松TLE(乐)

奇妙性质：对于任意一点\(k\),哈密顿路径中\(i\)到\(j\)可以拆为\(k\)到\(i\)和\(k\)到\(j\)(如果存在这条路径，那么一定经过每一个点)

我们钦定\(1\)为\(k\)点,点对\((i,j)\)的路径相当于\((i,1)\)和\((1,k)\)两条路径拼接得到

设计新dp:\(dp[i][st]\)表示从1出发到\(j\)状态为\(st\)(\(st\)意义同上)是否可行

转移枚举下一个点即可

我们优化掉了一维，且\(st\)的状态少一半(不用压第一个点)

复杂度:\(O(n2^n)\)，依然爆炸

取不来小标题

发现dp仅存储可不可行，浪费了

我们再压dp:\(dp[st]\)状态为\(st\)(\(st\)意义同上的上),可以到的点的状压(dp状态、值虽然都是\(2^n\)状压，但意义不同)

这样就是\(O(n2^n)\)了

考虑统计答案

我们要统计\(n^2\)个点对\((i,j)\)是否可行

鸽了