题目描述

给定一张 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

分析

首先从题目样例来看默认了涉及的图都是无向完全图（但是题目本身并未提及完全图，坑）。也就说，任意一点都可以直达其它顶点，这对题意的理解很重要，也就是说，我们完全不用担心从一个顶点到另一个顶点没有边，只需要枚举n个顶点的遍历顺序即可，暴力枚举是全排列，NP完成问题无法承受。所以使用状态压缩来提高下效率。

题目要求的是从起点0到终点n-1的最短Hamilton路径，从起点到当中任意一点都有一个最短路径，这些状态的区别仅在于当前遍历到的顶点，中间经过了哪些点以及路径的长度是多少？所以我们可以用f[i][j]表示从起点0走到顶点j路径为i的最短Hamilton路径长度。路径用一串二进制数表示，比如11011表示走过了0,1,3,4顶点，这里状态枚举时y总在讲解可能忽略了一个问题，就是，既然f数组定义是从0顶点出发，那么状态二进制表示的最后一位必然是1，也就是说只需要枚举i是奇数的情况，这样可以使得程序的执行速度快了一倍。比如某时刻i = 11011，j = 3，说明从0到3中间经过了1,4两点，那么路径就有两种0143和0413，我们找到其中路径长度的较小者就是f数组的值。状态转移方程为f[state][j] = f[state_k][k] + v[k][j]. f[state_k][k]表示当前在k顶点且从原来的顶点集中除去顶点k的情况，也就是说通过对倒数第二个顶点的枚举去寻求最小值。

另外，由于i只是表示哪些顶点已经遍历了，并不能表示遍历的顺序，因此，我们在遍历每个状态时，还需要枚举下当前遍历到的顶点，比如i = 11011，f[i][1]表示当前遍历到了顶点1，f[i][3]表示当前遍历到了顶点3，f[i][4]表示当前遍历到了顶点4，因此枚举到路径i时，我们需要将所有的状态都计算一遍。例如计算f[i][3]，我们要枚举倒数第二个顶点是什么，先去掉终点3得到10011，然后我们枚举倒数第二个点是1还是4，这时还剩下3个点，0是起点，必然不是倒数第二个点，除非去掉终点后的状态是00001，这时才需要以起点为倒数第二个点进行状态转移。故第二个要注意的是，只有路径中仅包含两个顶点时枚举k时才需要枚举0，否则不需要。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20,M = 1 << 20;
int n;
int f[M][N],v[N][N];
int main(){
    cin>>n;
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++){
            cin>>v[i][j];
        }
    }
    memset(f,0x3f,sizeof f);
    f[1][0] = 0;//还在0点的状态
    for(int i = 1;i < 1 << n;i++){
        if(i % 2 == 0)  continue;//路径必然包含起点
        for(int j = 0;j < n;j++){
            if(i >> j & 1){//枚举当前点
                int t = i - (1 << j);//去掉当前点
                int s = (t - 1 != 0);//如果只剩下了起点，才需要枚举以k = 0的情况
                for(int k = s;k < n;k++){
                    if(t >> k & 1){//以k为倒数第二个点
                        f[i][j] = min(f[i][j],f[t][k] + v[k][j]);
                    }
                }
            }
        }
    }
    cout<<f[(1<<n)-1][n-1];
    return 0;
}