最短Hamilton路径
最短Hamilton路径
题目链接
题目概述
对于一个 n ( n ≤ 20 ) n(n\leq 20) n(n≤20)个点的带权无向图,从 0 0 0开始标号到 n − 1 n-1 n−1,计算从起点0到终点 n − 1 n-1 n−1的最短 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 n−1不重复不遗漏的经过每一个点恰好一次.
题目分析
对于 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<<n−1;然后对此时状态 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 n−1的最短 H a m i l t o n Hamilton Hamilton路径,即F[(1<<n) - 1][n-1]
关键的位运算语句添加了详细的注释解释作用.
常见的位操作的:
- KaTeX parse error: Expected 'EOF', got '&' at position 10: (n >> k) &̲ 1:取出 n n n在二进制下的第 k k k位;
- KaTeX parse error: Expected 'EOF', got '&' at position 3: n &̲ ((1 << k)-1):取出整数 n n n在二进制下的后 k k k位;
- n x o r ( 1 < < k ) n\,xor\,(1 << k) nxor(1<<k):整数 n n n在二进制表示下的第 k k k位取反;
- n ∣ ( 1 < < k ) n\,|\,( 1 << k) n∣(1<<k):将整数 n n n在二进制表示下的第 k k k设置为1;
- 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
下一篇: 2020-09-21
推荐阅读
-
thinkphp如何禁止直接通过路径访问?
-
require中使用绝对路径的有关问题:常量重定义,变量覆盖,重调用增加开销
-
javascript - php 有什么函数是可以根据文件名称,来获取这个文件的全路径的吗?或者js 怎么获取文件的全路径?
-
kali linux 常用文件与指令路径
-
通过 vagrant 在 ubuntu 环境下安装 discuz X3 系列成功,但静态文件路径错误
-
PHP爆绝对路径方法收集整理
-
EFCore的外键级联删除导致的【可能会导致循环或多重级联路径】
-
解决vue-cli webpack打包后加载资源的路径问题
-
realpath自动清除路径中的点号
-
使用PHP计算两个路径的相对路径