这个问题实际上改写了 one . code jam problem是以下内容:
给你一个完整的无向图，有 N 个节点和 K 个“禁止”边。 N <= 300, K <= 15.求图中不使用任何K“禁止”的哈密顿循环数"边缘。
O(2^N*N^2) 的直接 DP 方法不适用于这样的 N。看来中奖了solutions是 O(2^K)。有谁知道如何解决这个问题？
最佳答案
让我们找出禁止边的每个子集 S，存在多少个使用 S 的所有边的哈密顿循环。如果我们解决这个子任务，那么我们将通过 inclusion-exclusion formula 解决问题。 .
现在我们如何解决子任务？让我们绘制S的所有边。如果存在一个度数大于2的顶点，那么显然我们无法完成循环，答案为0。否则图被划分为连通分量。每个组件都是一个顶点、一个循环或一条简单的路径。
如果存在环路，那么它必须通过所有顶点，否则无法完成哈密顿环路。如果是这样，则答案为2。(循环可以在2个方向上遍历。)否则答案为0。
剩下的情况是有c条路径和k个唯一顶点。要完成哈密顿循环，我们必须选择每条路径的方向(2^c 方式)，然后选择组件的顺序。我们有 c+k 组件，所以它们可以按 (c+k)! 方式重新排列。但是我们对循环感兴趣，所以我们不区分通过循环移位变成彼此的顺序。 (所以(1,2,3)，(2,3,1)和(3,1,2)是一样的。)这意味着我们必须将答案除以移位数，c+k 。所以(子任务的)答案是2^c (c+k-1)!。
这个想法在 bmerry 的解决方案中实现(非常干净的代码，顺便说一句)。
关于algorithm - 如何找到不使用 "forbidden"边的哈密顿循环数？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4759955/