首先說明一下，此博文來自我在CSDN上看到的一篇哈密頓回路（有向圖中）的位運算算法，出自GDTZX大神之手，（侵刪），雖然剛從校園畢業(yè)，但腦子已經(jīng)完全僵住了，花了許久才看懂了這個算法。

哈密頓回路，具體到本題之中即從某一個點開始經(jīng)過所有的點一次后再回到該點的不同路徑數(shù)。對于這個不同需要注意兩點：

如果我們將路徑經(jīng)過的點按順序?qū)懴拢热绠攏=3時，若存在123和231。此時，我們認為這兩條路徑是同一條哈密頓回路。而123和213則是不同的哈密頓回路。

若兩個點之間有多條邊，經(jīng)過不同的邊的路徑仍然看作同一條哈密頓回路。不同哈密頓回路只和經(jīng)過的點有關(guān)。因此對于多條邊的情況我們可以將其合并為一條邊來考慮。

對于哈密頓回路，一個簡單的想法就是枚舉所有可能的路徑，判定這個路徑是否存在。即時間復雜度為O(n!)。而題目給定的數(shù)據(jù)范圍為：n <= 12，所以最大可能的枚舉次數(shù)為12! = 479,001,600。

極限的數(shù)據(jù)不到5億，所以我們可以考慮使用暴力來枚舉所有的哈密頓回路。直接采用DFS枚舉我們的每一步，最后判定是否走回到起點。

偽代碼如下：

DFS(int nowVertex, bool visitedVertex, int path, int length)
    visitedVertex[ nowVertex ] = True;
    If (all Vertex is visited) Then
        Count = Count + 1
    Else 
        For (u is next vertex of nowVertex)
            If (not visitedVertex[ u ]) Then
                path[ length ] = u
                DFS(u, visitedVertex, path, length + 1)
            End If
        End For    
    End If
    visitedVertex[ nowVertex ] = False

由于哈密頓回路始終會經(jīng)過每一個點，所以我們只以1為起點就一定可以找出所有的哈密頓回路。

那么這樣是否能夠解決這道題目呢？我只能說不一定能夠解決。

雖然偽代碼相同，但是根據(jù)實現(xiàn)的方法會有不同的運行效率，在某些實現(xiàn)方法下就能夠通過所有的數(shù)據(jù)點，在某些實現(xiàn)方法下就會超過時限。

這里我們介紹一種利用位運算的實現(xiàn)，能夠使得整個程序的效率提高很多倍。

首先來看看代碼：

const int MAXN = 14;

int edge[ MAXN ];
int p[1 << MAXN];
int cnt;

void dfs(int nowVertex, int unused) {
    if (!unused) {
        cnt += (edge[nowVertex] & 1);
        return ;
    }
    int rest = unused & edge[ nowVertex ];
    while (rest) {
        int tp = rest & (-rest);
        dfs(p[ tp ], unused - tp);
        rest -= tp;
    }
    return ;
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i)
        p[ 1 << i ] = i + 1;
    while (m--) {
        int u, v;
        scanf("%d %d", &u, &v);
        edge[u] |= 1 << (v - 1);
    }
    dfs(1, (1 << n) - 2);
    printf("%dn", cnt);
    return 0;
}

我們一個一個來解釋每一個變量的含義：

edge[i]表示點i的next節(jié)點情況，我們用二進制表示edge[i]，比如當edge[i]=01011時：

+---+---+---+---+---+
| 5 | 4 | 3 | 2 | 1 | 右起第j位
+---+---+---+---+---+
| 0 | 1 | 0 | 1 | 1 | 二進制位的值
+---+---+---+---+---+

從右起第j位，若為1，則表示存在i到j(luò)的邊；若為0，則表示不存在i到j(luò)的邊。所以edge[i]=01011就表示節(jié)點i可以到達節(jié)點1，2，4。

p[i]是為了方便查找點的編號。在edge[i]中若存在01000，我們可以根據(jù)01000=8, 而p[8]=4來快速的通過二進制位來定位節(jié)點編號。

所以有初始化：

for (int i = 0; i < n; ++i)
    p[ 1 << i ] = i + 1;

而通過節(jié)點編號來找到二進制位，則可以直接使用1 << (i - 1)實現(xiàn)。

我們在讀入數(shù)據(jù)時，通過位運算邊可以記錄下所有點之間的連邊情況：

while (m--) {
    int u, v;
    scanf("%d %d", &u, &v);
    edge[u] |= 1 << (v - 1);    // 記錄u有后繼節(jié)點v
}

unused該二進制數(shù)表示我們尚未訪問的節(jié)點集合，同樣的右起第i位表示節(jié)點i，比如unused = 01100：

+---+---+---+---+---+
| 5 | 4 | 3 | 2 | 1 | 右起第i位
+---+---+---+---+---+
| 0 | 1 | 1 | 0 | 0 | 二進制位的值
+---+---+---+---+---+

表示我們現(xiàn)在深度優(yōu)先搜索已經(jīng)經(jīng)過了節(jié)點1,2,5，而節(jié)點3,4還尚未經(jīng)過。

由于我們是以節(jié)點1作為起點，初始化的unused也就要去掉最右邊的1，所以代碼為dfs(1, (1 << n) - 2)。

接下來我們逐行解釋dfs函數(shù)：

if (!unused) {
    cnt += (edge[nowVertex] & 1);
    return ;
}

當我們所有的節(jié)點都經(jīng)過一次之后，unused中一定不存在1，因此有!unused = true。但是此時并不一定找到了哈密頓回路，我們還需要判斷當前節(jié)點是否能回到起點，也就是節(jié)點1。若nowVertex可以到達節(jié)點1，則edge[nowVertex]最右邊1位一定是1，那么就一定有edge[nowVertex] & 1 = 1。

int rest = unused & edge[ nowVertex ];

rest表示當前節(jié)點還可以走到的未訪問節(jié)點。由于&運算的性質(zhì)，只有當unused和edge[ nowVertex ]對應(yīng)二進制位同時為1時，rest對應(yīng)的二進制位才會為1。其含義就是該節(jié)點尚未訪問，且節(jié)點nowVertex可以到達該節(jié)點。

while (rest) {
    int tp = rest & (-rest);
    dfs(p[ tp ], unused - tp);
    rest -= tp;
}

該循環(huán)的作用是枚舉每一個可以到達的點。

int tp = rest & (-rest);

這里利用了一個性質(zhì)，即p & -p等于取出p的最右邊的一個1。舉個例子p=10110:

   +---+---+---+---+---+
p  | 1 | 0 | 1 | 1 | 0 | 
   +---+---+---+---+---+
-p | 0 | 1 | 0 | 1 | 0 | 
   +---+---+---+---+---+
&  | 0 | 0 | 0 | 1 | 0 | 
   +---+---+---+---+---+

我們不斷的利用這個性質(zhì)從rest里面取出可以使用的二進制位，進行dfs(p[ tp ], unused - tp);。同時再枚舉完一個節(jié)點后，將其從rest中刪除，即rest -= tp;。

最后我們再使用printf("%dn", cnt);來輸出我們找到的方案數(shù)。

在上面DFS的基礎(chǔ)上，我們還可以進一步優(yōu)化。

遞歸的過程中，unused很有可能會出現(xiàn)重復的情況，比如說從1->3->2->4和從1->2->3->4，對于dfs(4, unused)來說，此時的unused值都是相同的。因此我們可以采用記憶化搜索的方式進一步降低復雜度。

定義數(shù)組f[n][unused]表示當前節(jié)點為n，且節(jié)點訪問情況為unused時的方案數(shù)量。

那么有：

f[n][unused] = sigma(f[p][unused + (1 << (n - 1))] | (unused & (1 << (n - 1)) == 0) and (p != n) and (edge[p] & (1 << (n - 1)) != 0))

這對應(yīng)的是原dfs函數(shù)中下面這段代碼的逆過程。

while (rest) {
    int tp = rest & (-rest);
    dfs(p[ tp ], unused - tp);
    rest -= tp;
}

三個條件分別為：

在計算f[n][unused]的過程中，假設(shè)unused的二進制表示中有i個1，則我們需要事先計算出所有i+1個1的狀態(tài)才能夠保證unused + (1 << (p - 1))是正確的結(jié)果。

因此我們在枚舉過程中，需要按照狀態(tài)中1的個數(shù)來枚舉。

其偽代碼：

For numberOfOnes = n-1 .. 0
    For (the number of ones of unused equals numberOfOnes)
        For nowVertex = 1 .. n
            For prevVertex = 1 .. n
                If (unused & (1 << (nowVertex - 1)) == 0) and (prevVertex != nowVertex) and (edge[ prevVertex ] & (1 << (nowVertex - 1)) != 0) Then
                    f[ nowVertex ][ unused ] = f[ nowVertex ][ unused ] + f[ prevVertex ][unused + (1 << (nowVertex - 1))]
                End If
            End For
        End For
    End For
End For

對于f[n][ unused ]數(shù)組，其初始條件為f[1][(1 << n) - 2] = 1。

最后需要將所有的f[n][0]中能夠到達節(jié)點1的節(jié)點n累加起來，即可得到所有的方案數(shù)。該算法的理論時間復雜度為O(2^n*n^2)。

該題目一共只有7名選手通過，大部分提交過該題的選手也都有一定的部分分值。

本題直接采用搜索就能夠通過，拉開差距的主要原因是對于偽代碼實現(xiàn)方式的不同，而導致通過的測試點數(shù)量不同。

另外還有一個易錯點是走完所有節(jié)點之后一定要判斷是否可以回到起點。