AcWing 91. 最短Hamilton路径

2023-09-10 04:31| 来源: 网络整理| 查看: 265

题目描述

给定一张 $n$ 个点的带权无向图，点从 $0 \sim n-1$ 标号，求起点 $0$ 到终点 $n-1$ 的最短 $Hamilton$ 路径。 $Hamilton$ 路径的定义是从 $0$ 到 $n-1$ 不重不漏地经过每个点恰好一次。

输入格式

第一行输入整数 $n$。

接下来 $n$ 行每行 $n$ 个整数，其中第 $i$ 行第 $j$ 个整数表示点 $i$ 到 $j$ 的距离（记为 $a[i, j]$）。

对于任意的 $x, y, z$，数据保证 $a[x, x] = 0$，$a[x, y] = a[y, x]$ 并且 $a[x, y] + a[y, z] \geq a[x, z]$。

输出格式

输出一个整数，表示最短 $Hamilton$ 路径的长度。

数据范围

$1 \leq n \leq 20$ $0 \leq a[i, j] \leq 10 ^ 7$

输入样例： 5 0 2 4 5 1 2 0 6 5 3 4 6 0 8 3 5 5 8 0 5 1 3 3 5 0 输出样例： 18 算法 (状态压缩DP) $O(n^2)$

首先想下暴力算法，这里直接给出一个例子。比如数据有 $5$ 个点，分别是 $0, 1, 2, 3, 4$ 那么在爆搜的时候，会枚举一下六种路径情况（只算对答案有贡献的情况的话）：

$case\ 1:\ 0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ $case\ 2:\ 0 \rightarrow 1 \rightarrow 3 \rightarrow 2 \rightarrow 4$ $case\ 3:\ 0 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 4$ $case\ 4:\ 0 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 4$ $case\ 5:\ 0 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 4$ $case\ 6:\ 0 \rightarrow 3 \rightarrow 2 \rightarrow 1 \rightarrow 4$

那么观察一下 $case\ 1$ 和 $case\ 3$，可以发现，我们在计算从点 $0$ 到点 $3$ 的路径时，其实并不关心这两中路径经过的点的顺序，而是只需要这两种路径中的较小值，因为只有较小值可能对答案有贡献。所以，我们在枚举路径的时候，只需要记录两个属性：当前经过的点集，当前到了哪个点。而当前经过的点集不是一个数。观察到数据中点数不会超过 $20$，我们可以用一个二进制数表示当前经过的点集。其中第 $i$ 位为 1/0 表示是/否经过了点 $i$。然后用闫式 dp 分析法考虑 dp 状态表示：$f[state][j]$。其中 $state$ 是一个二进制数，表示点集的方法如上述所示。

集合：经过的点集为 $state$，且当前到了点 $j$ 上的所有路径。属性：路径总长度的最小值

状态计算：假设当前要从点 $k$ 转移到 $j$。那么根据 $Hamilton$ 路径的定义，走到点 $k$ 的路径就不能经过点 $j$，所以就可以推出状态转移方程f[state][j] = min{f[state ^ (1

【本文地址】

公司简介

联系我们