题目
给定一张 n 个点的带权无向图,点从 0∼n−1 标号,求起点 0 到终点 n−1 的最短 Hamilton 路径。
Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。
数据范围
1≤n≤20
0≤a[i,j]≤107
思路(推荐看看,也可以跳过看代码)
相当于已经知道有下标从0开始的n个点。
求所有经过每个点恰好一次的路径集合中的路径最短长度。注意起点和终点是固定的
先暴力想想:每个点只能出现一次,那可以先固定起点和终点然后来一个全排列呀
0 x x x … x x x (n - 1) 最多有18个x
18 * 17 * 16 * … * 2 * 1 = 18! = 6.4 * 10^15 (远远大于 5 * 10 ^ 8)
看来暴力是行不通的!
之所以不通,大概是它每个点都枚举一遍!
怎么办? 状态压缩。
运用状态压缩, 可以用一个整数枚举全部点。
状态表示f[i][j]
:表示所有经过的点集为i,终点为j的路径,属性是最短路径长度
划分依据:利用倒数第二个点k
状态计算:f[i][j] = min(f[i & ~(1 << j)][k] + w[k][j])
i & ~(1 << j) == i ^ 1 << j == i - (1 << j)
表示已 经过的点集中去掉点j
因为我们还没走到j这个点
f[i & ~(1 << j)][k]
:经过的点集为i & ~(1 << j)终点为k的所有路径,属性是最短路径长度
再 + w[k][j]代表经过k再走到j的最短路径长度,如果比原来的短就更新
答案是 f[(1 << n) - 1][n - 1]
1 << n
相当于1000..00 有n个0
-1 表示 111…11 有n个1, 表示0..n-1所有n个点都经过
表示0..n-1所有n个点都经过,终点是n-1,起点是0的最短路径长度
状态初始化: f[1..1<<n][0..n-1] = INF, f[1][0] = 0;
要求最小值,先定义任意点集到达任意终点的距离为无穷大。
1代表000…001, 只经过点0,终点为0的路径长度为0
感觉还挺像floyd。
二进制运算相关概念
任何数 & 1 = 本身
任何数 & 0 = 0
任何数 ^ 1 = 相反数
任何数 ^ 0 = 本身
~任何数 = 二进制位相反的数
<< >> 二进制位的左移 右移
运算符优先级:-,!,~ >> *,/,% >> >>,<< >> >,<,>=,<= >> ==,!= >> & >> ^ >> | >> && >> || >> 问号表达式 >> 赋值语句
时间复杂度
2^20 * 20 * 20 = 410^8 < 510^8 勉强过了
但对比暴力是一个质的飞跃!!
代码附注释
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 20, M = 1 << 20;
int n;
int w[N][N];//两点之间的距离
int f[M][N];//状态表示,第一个维度是点集的状态,第二个维度是终点。
//点集状态为什么又 1 << 20 个? 因为每个点都有选与不选两种情况,最多有20个点。
int main()
{
//数据读入
cin >> 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;
//状态转移计算
for (int i = 1; i < 1 << n; i ++ ) //遍历每一种点集00..01 -> 11..11
if (i & 1) // 必须包含起点0的点集
for (int j = 1; j < n; j ++ ) //遍历每一个终点,1..n - 1
if (i >> j & 1) // 如果点集里包含这个终点
for (int k = 0; k < n; k ++ )//遍历点集中除了终点的点
if ((i >> k & 1) && k != j) // 点集里有点k,且点k不是j
if (f[i][j] > f[i ^ 1 << j][k] + w[k][j]) //可以更新就更新
f[i][j] = f[i ^ 1 << j][k] + w[k][j];
//结果输出
cout << f[(1 << n) - 1][n - 1] << endl;//输出最短 Hamilton 路径的长度。
return 0;
}