CH0103最短Hamition路径 （状压DP）状压杀我呜呜呜

给定一张 n 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。

输入格式
第一行输入整数n。

接下来n行每行n个整数，其中第i行第j个整数表示点i到j的距离（记为a[i,j]）。

对于任意的x,y,z，数据保证 a[x,x]=0，a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]>=a[x,z]。

输出格式
输出一个整数，表示最短Hamilton路径的长度。

数据范围

1≤n≤20

0≤a[i,j]≤107

输入样例：

5

0 2 4 5 1

2 0 6 5 3

4 6 0 8 3

5 5 8 0 5

1 3 3 5 0

输出样例：

18

如果考虑DP的话，那么应该如何划分状态？
首先需要确定我们要考虑的因素，因为Hamiton路径每个点只能经过一次，并且要经过所有的点，所以我们应该考虑当前的状态经过哪些点，但是如果只考虑当前经过哪些点的话，我们没有办法确定当前的最短路径是多少，即我们不知道我们是从哪个点转移过来的，那么我们就需要考虑我们当前所在的是哪个点，那么我们就可以知道我们从哪里转移过来，边权是多少，我们就可以更新我们的最短路。

我们需要考虑的因素：

1.当前经过哪些点

2.当前在那哪个点

那么我们就应该考虑状态：

我们用$f[i][j]$表示当前的状态，其中i是当前所经过点的集合，j是当前所在的点。

考虑完状态之后我们就需要考虑如何转移：

因为每两个点之间都存在路径，所以我们可以从任意一个点转移过来，但是我们要确保向当前状态转移的状态的当前状态点没有访问且访问了向当前状态转移的状态的点。

即：

$f[i][j] = min([state_k][k]+w[k][j],f[i][j])$

其中$state_k$ $j$未被访问，且包括$k$这个点。

换言之就是$state_k$为集合$i$中$j$未被访问，但$k$被访问的集合，这样就与当前状态建立了联系。

那么我们首先可以枚举集合$i$,即枚举通过的点来扩展状态。

接下来我们可以通过枚举合法的$j$与合法的$k$来确定状态的最优解。

$j$合法：即$i$集合中包括$j$。

$k$合法：即$i$集合中$k$已被访问。

那么我们用什么来确定每个点是否被访问？

因为数据规模比较小，所以我们可以用一个32位二进制整数n的第i位来保存第i个点是否被访问。

状态压缩

二进制状态压缩，是将一个长度为m的bool数组用一个m位二进制整数表示存储的方法。可以利用如下的方法实现原bool数组对应下表的存取。

那么我们就可以得到完整的状态转移方程：

$f[i][j] = min(f[i xor(1<<j)][k] + w[k][j],f[i][j])$

且满足于$(i >> j) $ & $ 1 = 1$

$(i xor (i << j)) >> k $ & $1 = 1$

其中，$(i >> j) $ & $ 1 = 1$（是确保当前状态下i的第$j$位一定为1，即$j$点被访问。

而 $i xor(1<<j)$则代表将$i$的第$j$位取反 即在$i$中$j$未被访问（其余不变）的状态。

其复杂度为$O(2^n*n)$

#include <iostream>
#include <cstring>
using namespace std;
int f[1 << 20][25],w[25][25],n;
int main(){
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> w[i][j];

    memset(f,0x3f,sizeof(f));
    f[1][0] = 0;
    for (int i = 0; i <= 1 << n; i++){
        for (int j = 0; j < n; j++){
            if (i&(1<<j) == 1 << j){
                for (int k = 0; k < n; k++){
                    if ((i^1<<j) >> k & 1){
                        f[i][j] = min(f[i][j],f[i^1<<j][k] + w[k][j]);
                    }
                }
            }
        }
    }
    cout << f[(1<<n)-1][n - 1];
    return 0;
}