GCJ - 哈密顿圈 [英] GCJ - Hamiltonian Cycles

问题描述

code拥堵问题如下：

您将得到一个完整的无向图有N个节点和K禁止入内的边缘。 N'其中; = 300，K＆其中; = 15，查找哈密顿周期在图中不使用任何在K禁边缘

You are given a complete undirected graph with N nodes and K "forbidden" edges. N <= 300, K <= 15. Find the number of Hamiltonian cycles in the graph that do not use any of the K "forbidden" edges.

不幸的是这这里堆栈和整个网络的解释是很不够的。我可以找出HamCycles一定'N'（N-1）！ / 2

Unfortunately the explanations of this here on stack and throughout the web are very insufficient. I can figure out HamCycles for a certain 'n' : (n-1)! / 2 .

和我可以做短一套具有动态规划。

And I can do the short set with dynamic programming.

不过，我没有得到所有的子集博洛尼亚，如何使它o ^ K'我在Python和尚未破译的C ++使用。最后，我敢肯定，我会花时间去学习C ++的，然后我将破译它。但在此期间，我为什么不能有人解释这更好的地方在网络上？他们总是一半的解释。

But I don't get all the subset bologna, how to make it O^K? I'm in Python and have yet to decipher the C++ available. Eventually I'm sure I will take the time to learn C++ and then I will decipher it. But in the meantime, why can't someone explain this better somewhere on the web? They are always half explanations.

推荐答案

这可能会帮助，如果你指向缺乏的解释，但我会想试试...

It might help if you point to the explanations that are lacking, but I'll try anyway...

在O（2 ^K ） - 基础的解决方案使用的容斥原理。鉴于氏/ EM> 2 ^K 的那些有 禁止的边缘，还有的的 子集边缘，包括其本身和空集。例如，如果有3禁止边缘：{A，B，C}，将有2 ³ = 8的子集：{}，{A}，{B}，{c}里，{ A，B}，{A，C}，{B，C}，{A，B，C}。

The O(2^k)-based solution uses the inclusion-exclusion principle. Given that there are k forbidden edges, there are 2^k subsets of those edges, including the set itself and the empty set. For instance, if there were 3 forbidden edges: {A, B, C}, there would be 2³=8 subsets: {}, {A}, {B}, {C}, {A,B}, {A,C}, {B,C}, {A,B,C}.

有关每个子集，则计算周期包括至少所有在该子集的边缘的数量。如果包含的周期数边缘的的取值的是 F（S）的和的取值 是集中所有禁止的边缘，然后由容斥原理，周期没有任何禁止边数为：

For each subset, you calculate the number of cycles that include at least all the edges in that subset . If the number of cycles containing edges s is f(s) and S is the set of all forbidden edges, then by the inclusion-exclusion principle, the number of cycles without any forbidden edges is:

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

在哪里| 取值的 |是元素的个数的的取值的。换句话说，周期与任何边的数目的总和的减去的周期与至少1禁止边缘数量的加的具有至少2个被禁止的边缘的数量，。 ..

where |s| is the number of elements in s. Put another way, the sum of the number of cycles with any edges minus the number of cycles with at least 1 forbidden edge plus the number with at least 2 forbidden edges, ...

计算的的 F（S）的是不平凡的 - 至少我没有找到一个简单的方法来做到这一点。你可能会停下来阅读之前深思。

Calculating f(s) is not trivial -- at least I didn't find an easy way to do it. You might stop and ponder it before reading on.

要计算的的 F（S）的，开始并未参与任何的的取值的节点。如果有 M 的这样的节点，还有的的 M 的！排列，你也知道。呼叫排列数的的 C 的

To calculate f(s), start with the number of permutations of the nodes not involved with any s nodes. If there are m such nodes, there are m! permutations, as you know. Call the number of permutations c.

现在检查的边缘的的取值的作为链。如果有任何不可能的组合，如涉及3边或在子周期的一个节点的的取值的和的 F（S）的 0

Now examine the edges in s for chains. If there are any impossible combinations, such as a node involved with 3 edges or a subcycle within s, then f(s) is 0.

否则，对于每个链增量的的 M 的按1和繁殖的的 C 的按 2米的。 （有 M 的地方放环比现有的排列和2的因素是因为链条可以向前或向后）。最后， F（S）的是 C 的 /（ 2米的）。最后的分裂排列转化为周期。

Otherwise, for each chain increment m by 1 and multiply c by 2m. (There are m places to put the chain in the existing permutations and the factor of 2 is because the chain can be forwards or backwards.) Finally, f(s) is c/(2m). The last division converts permutations to cycles.

这篇关于GCJ - 哈密顿圈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！