完全图的最短Hamilton路径——状压dp

题意：给出一张含有n（n<20）个点的完全图，求从0号节点到第n-1号节点的最短Hamilton路径。Hamilton路径是指不重不漏地经过每一个点的路径。

　　算法进阶上的一道状压例题，复杂度为O(n^2 * 2^n)，还是蛮恐怖的。

　　设f[i][j]表示当前经过状态为i，且当前在点j所花费的最小代价。其中i是二进制压缩值，从0～n-1位分别表示这个点是否经过了。目标状态为f[2^n - 1][n - 1]，那么我们从小到大枚举i，再循环枚举当前点j和上一个状态所在的点k即可。

　　转移方程：f[i, j] = min(f[i xor 2^j, k] + edge_weight[k, j])。其中i xor 2^j可以从i表示的状态中去掉第j位。需要注意的是，枚举j、k的时候要特判选择它是否符合当前状态。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int f[1 << 20][20], w[20][20], n;
int hamiton() {
    memset(f, 0x3f, sizeof(f));
    f[1][0] = 0;
    for (int i = 1; i < (1 << n); ++i)
        for (int j = 0; j < n; ++j) if (i >> j & 1)
            for (int k = 0; k < n; ++k) if ((i xor 1 << j) >> k & 1)
                f[i][j] = min(f[i][j], f[i xor 1 << j][k] + w[k][j]);
    return f[(1 << n) - 1][n - 1];
}
int main() {
    cin >> n;
    int t;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j) {
            cin >> t;
            w[i][j] = t;
        }
    cout << hamiton();
    return 0;
}