欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

最短Hamilton路径

程序员文章站 2022-06-21 19:13:53
最短Hamilton路径题目链接牛客ACwing题目概述对于一个n(n≤20)n(n\leq 20)n(n≤20)个点的带权无向图,从000开始标号到n−1n-1n−1,计算从起点0到终点n−1n-1n−1的最短HamiltonHamiltonHamilton路径,HamiltonHamiltonHamilton路径是从000到n−1n-1n−1不重复不遗漏的经过每一个点恰好一次.题目分析对于nnn个点,如果直接枚举所有排列的可能性,有n!n!n!种可能性.利用正整数的二进制位的特征来表示每个...

最短Hamilton路径

题目链接

牛客
ACwing

题目概述

对于一个 n ( n ≤ 20 ) n(n\leq 20) n(n20)个点的带权无向图,从 0 0 0开始标号到 n − 1 n-1 n1,计算从起点0到终点 n − 1 n-1 n1的最短 H a m i l t o n Hamilton Hamilton路径, H a m i l t o n Hamilton Hamilton路径是从 0 0 0 n − 1 n-1 n1不重复不遗漏的经过每一个点恰好一次.

题目分析

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

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

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

最后的结果就是所有点都经过且此时位于最后一个点 n − 1 n-1 n1的最短 H a m i l t o n Hamilton Hamilton路径,即F[(1<<n) - 1][n-1]

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

常见的位操作的:

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