GCJ Practice Contest Problem C:
In this problem, u r asked to calculate the number of all the Hamiltonian Circles in complete graph only with at most 15 forbidden edges.
We know, finding the Hamiltonian Circles is a NP problem, how can we count all the Hamiltonian Circles in a graph with so many edges?
First, let us think about this problem. Give u a complete graph with N vertexes , can u tell me how many Hamiltonian Circles exist in it?
We can easily find that number will be (N-1)! / 2.
And back to the original problem, we find that the forbidden edges are very small. So we come up with an idea, we can use the number of Hamiltonian Circles in a complete graph minus those circles using forbidden edges.
Code
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。