GCJ - 哈密顿循环 [英] GCJ - Hamiltonian Cycles

问题描述

代码堵塞问题如下:

给定一个完整的无向图，其中包含 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.

不幸的是，在堆栈和整个网络上对此的解释非常不够.我可以找出某个 'n' 的 HamCycles:(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.

但是我没有得到所有的子集 bologna，如何使它 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) 的解决方案使用 包含-排除原则.鉴于有 k 个禁止边，有 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}.

对于每个子集，您计算至少包含该子集中所有边的循环数.如果包含边s的循环数是f(s)和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|

哪里 |s|是 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)，从不涉及任何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.

现在检查s 中链的边缘.如果在s内有任何不可能的组合，例如涉及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/(2m).最后一个除法将排列转换为循环.

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屋！