最短Hamilton路径

最短Hamilton路径

题目大意

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

思路

暴力超时，所以考虑二进制、状态压缩等思路。在 $1<<n$ 的范围内的每一个数的二进制都是一种选择方案。$0$ 表示未到达， $1$ 表示到达，枚举每一种方案中每一个点到达情况的状态转移。

int f[ 1 << 20][22],weight[22][22];
void solve()
{
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> weight[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 >> j & 1)) {//是否为 1，1则表示这个点已经走过
                for (int k = 0; k < n; k++) {//枚举哪些点到达 j, i -> j --- k -> j
                    if (i ^ (1 << j) >> k & 1) {//同理，找没到达j点的情况，从k走到j 1 ^ 1 = 0，将第j位变为0
                        f[i][j] = min(f[i][j], f[i ^ (1 << j)][k] + weight[k][j]);
                    }
                }
            }
        }
    }
    cout << f[(1 << n) - 1][n - 1] << endl;
}