最短Hamilton路径

题目链接

牛客
ACwing

题目概述

对于一个$n(n\le 20)$个点的带权无向图,从$0$开始标号到$n-1$,计算从起点0到终点$n-1$的最短$Hamilton$路径,$Hamilton$路径是从$0$到$n-1$不重复不遗漏的经过每一个点恰好一次.

题目分析

对于$n$个点,如果直接枚举所有排列的可能性,有$n!$种可能性.利用正整数的二进制位的特征来表示每个点的选择状态,如果经过第$i$个点,那么将第$i$个点设置为$1$,否则设置为$0$.

创建一个二维数组F[1<<n][n],F[i][j]表示在经过的点的状态表示的二进制数$i$状态下此时处于点$j$,即$j$是本轮新经过的点.

首先枚举经过点的所有可能状态,即从$1$遍历到$1<<n-1$;然后对此时状态$i$中每一个点,认为其是本轮新经过的点,然后从剩下的已经经过的点中选择一个$k$,在没有经过$j$点时并且此时处于$k$的最短$Hamilton$路径,即F[i << ( 1 << j)][k],新增一条从$k$到$j$的路径选择,与原来的经过$j$点并且此时处于$j$点,且经过的点组成的最短$Hamilton$路径F[i][j]中选择一个作为更新后的最短$Hamilton$路径.

最后的结果就是所有点都经过且此时位于最后一个点$n-1$的最短$Hamilton$路径,即F[(1<<n) - 1][n-1]

关键的位运算语句添加了详细的注释解释作用.

常见的位操作的:

1. KaTeX parse error: Expected 'EOF', got '&' at position 10: (n >> k) &̲ 1:取出$n$在二进制下的第$k$位;
2. KaTeX parse error: Expected 'EOF', got '&' at position 3: n &̲ ((1 << k)-1):取出整数$n$在二进制下的后$k$位;
3. $nxor(1<<k)$:整数$n$在二进制表示下的第$k$位取反;
4. $n|(1<<k)$:将整数$n$在二进制表示下的第$k$设置为1;
5. KaTeX parse error: Expected 'EOF', got '&' at position 3: n &̲ (~(1 << k)):将整数$n$在二进制表示下的第$k$设置为0.

代码

/*
 * @Author: Shuo Yang
 * @Date: 2020-09-22 18:59:23
 * @LastEditors: Shuo Yang
 * @LastEditTime: 2020-09-22 19:32:26
 * @FilePath: /Code/ICPC/基本算法/位运算/ch0103.cpp
 */
#include<bits/stdc++.h>
using namespace std;
const int N = 20;

int weights[N][N];
int f[1<<N][N];


// f[i][j]被经过的点以1表示组成的二进制数,并且此时处于点j时的最短路径
// 则题目要求的最短路径就是f[(1<<n)-1][n-1],即所有点都经过了,并且此时处于最后一个点
// 题目要求每一个点能并且只能经过一次.
int hamilton(int n){
    // memset是把这个段区间的每一个字节置为数c,对于0x3f是一个字节可以表示的最大的有符号的整数.
    memset(f, 0x3f, sizeof(f));

    f[1][0] = 0;
    // 枚举经过1个2个...n个点的所有可能性
    for(int i = 1; i < (1 << n); ++i){
        for(int j = 0; j < n; ++j){
            if((i >> j) & 1){    //表示当前表示经过点的状态的数i,此时处于点j
                for(int k = 0; k < n; ++k){
                    // 1 ^ (i<<j)表示将上一时刻经过的点j对应的二进制位设置为0
                    // 找出i ^ (1 << j) >> (k & 1)则从上一未经过点j的状态中那些位是1的点k,添加一条点k到点j的路径,看一看是否更短.
                    if(((i ^ (1 << j)) >> k) & 1)
                        f[i][j] = min(f[i][j], f[i^(1 << j)][k]  + weights[k][j]);
                }
            }
        }
    }
    return f[(1 << n) - 1][n-1];
}

int main(int argc, const char** argv) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin>>n;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j)
            cin>>weights[i][j];
    }
    cout<<hamilton(n)<<endl;
    return 0;
}

本文地址：https://blog.csdn.net/qq_43220622/article/details/108739769