最短Hamilton路径（二进制状态压缩）

题目描述：n个点的带权无向图，从0-n-1，求从起点0到终点n-1的最短Hamilton路径（Hamilton路径：从0-n-1不重不漏的每个点恰好进过一次）
题解：二进制状态压缩算法\(O(2^n*n^2)\)，需要记录当前经过了哪些点，当前在哪个位置。\(f[i][j]\) \(i\)转化为二进制每一位代表是否经过该点，\(j\)表示当前位于j这个点

#include <iostream>

#include <cstring>

using namespace std;

int f[1<<20][20];//0-19 location; status,loction

int w[20][20];

int main(){

    int n;scanf("%d",&n);

    for(int i=0;i<n;i++){

        for(int j=0;j<n;j++) {

            scanf("%d", &w[i][j]);

        }

    }

    memset(f,0x3f,sizeof(f));

    f[1][0]=0;

    int im=1<<n;

    int ps;

    for(int i=1;i<im;i++)

        for(int j=0;j<n;j++)if((i>>j)&1)//the previous status is available

         {

            ps=i^(1<<j);//the previous status

            for (int k = 0; k < n;k++)if(ps&(1<<k))//find the previous available location

                f[i][j] = min(f[i][j], f[ps][k] + w[k][j]);

         }

    printf("%d",f[(1<<n)-1][n-1]);

    return 0;

}

巴特西

# 最短Hamilton路径（二进制状态压缩）

最短Hamilton路径（二进制状态压缩）

最新文章

热门文章