我正在尝试这个 Google Codejam 问题，它说如果我们从完整图中删除 k 条边，可以找出汉密尔顿路径的数量
链接到问题
https://code.google.com/codejam/contest/32004/dashboard#s=p2
我发现我们可以使用包含排除原则来找出数字
但我的问题是当我们考虑从完整图中删除了一些“x”个边时如何确定路径数（给出了删除的边）
问问题
1612 次
1 回答
0
这个想法是计算排列而不是计算路径。这样，每条路径将被考虑 2*n 次。
如果排列是 n! 的总数。
让我们使用包含-排除原则来计算坏循环。如果一个边缘被禁止，则有 2*n * (n-2)！包含这条边的路径（我们将两个相邻的顶点放在一起，其余的去任何地方）。
如果有多个禁止边，则将所有顶点分成几个独立的组（它们形成由这些边连接的链）。有两种方法可以放置每个组（因为它可以颠倒）。所有组可以相互任意排列。其余元素可以放置在任何地方（它将作为二项式系数乘以一些阶乘）。还有一个警告：链条可以缠绕。但最多只能有一个这样的链。因此，我们可以使用上述算法遍历包裹并计算放置其余部分的方式的数量。
于 2017-01-17T09:38:23.120 回答