动态规划

显然答案是总哈密顿回路数除以值得记录的竞赛图数 那么先求解总哈密顿回路数，考虑每个哈密顿回路会在几个值得记录的竞赛图中，则有$$Hamitons = (n - 1)!2^{C_n^2 - n}$$即总共有 $(n - 1)!$ 种哈密顿回路，然后剩下的边随便选 于是现在考虑值得记录的竞赛图数 首先如果一个竞赛图要有哈密顿回路，那么它至少要有一个包含所有节点的环，即该图是强连通的，并且显然非强连通竞赛图它一定不存在哈密顿回路，所以有结论 有且仅有强连通竞赛图存在哈密顿回路 那么问题转化为求解强连通竞赛图 发现正面难以求解，就考虑反面求解 设 $f_n$ 表示 $n$ 个节点的强连通竞赛图数，$g_n$ 表示 $n$ 个节点的竞赛图数（即 $2^{C_n^2}$），可得 $DP$ 方程$$f_n = g_n - \sum\limits_{j = 1}^{n - 1} f_jg_{n - j}\dbinom{n}{j}$$其中求解非强连通竞赛图部分是每次将拓扑序最小的强连通分量提取出来计数，那么剩下的点随意连接（注意，此时取的是拓扑序最小的强联通分量，故该强联通分量与其它连通分量的连边方 ...