algorithm - GCJ - 哈密顿循环

Question

Code jam problem是以下内容:

给你一个完整的无向图，有 N 个节点和 K 个“禁止”边。 N <= 300, K <= 15。找出图中不使用任何 K 个“禁止”边的哈密顿循环数。

不幸的是，堆栈上和整个网络上对此的解释都非常不足。我可以计算出某个“n”的 HamCycles:(n-1)!/2 .

我可以用动态规划来做短集。

但是我没有得到所有的博洛尼亚子集，如何让它成为 O^K？我在 Python 中，还没有破译可用的 C++。最终我确定我会花时间学习 C++，然后我会破译它。但与此同时，为什么有人不能在网络上的某个地方更好地解释这一点？它们总是半解释。

Answer 1

如果您指出缺少的解释可能会有所帮助，但无论如何我都会尝试...

基于 O(2^k) 的解决方案使用 inclusion-exclusion principle .假设有 k 个禁止边，则有 2^k 个子集边，包括集合本身和空集。例如，如果有 3 个禁止边:{A, B, C}，则将有 2³=8 个子集:{}, {A}, {B}, {C}, { A,B}, {A,C}, {B,C}, {A,B,C}。

对于每个子集，您计算至少包含该子集中所有边的循环数。如果包含边s的循环数是f(s)和S 是所有禁止边的集合，则根据包含排除原理，没有任何禁止边的循环数为:

 sum, for each subset s of S: f(s) * (-1)^|s|

哪里 |s|是 s 中的元素数。换句话说，具有任何边的循环数之和减去具有至少 1 个禁止边的循环数加上具有至少 2 个禁止边的循环数，。 ..

计算 f(s) 并非易事——至少我没有找到一种简单的方法。在继续阅读之前，您可能会停下来思考一下。

要计算 f(s)，从不涉及任何 s 的节点的排列数开始 节点。如果有 m 个这样的节点，就有 m!排列，如你所知。将排列数称为 c。

现在检查 s 中的边缘是否有链。如果存在任何不可能的组合，例如包含 3 条边的节点或 s 内的子循环，则 f(s) 为 0。

否则，对于每个链递增 m 1 并将 c 乘以 2m。 (有 m 个地方可以将链放在现有排列中，因子 2 是因为链可以向前或向后。)最后，f(s) 是 c/(2m)。最后一个除法将排列转换为循环。