AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

AcWing 91. 最短Hamilton路径    原题链接    中等

作者: 作者的头像   秦淮岸灯火阑珊 ,  2019-01-17 11:24:09 ,  所有人可见 ,  阅读 13431


127


46

题目描述

给定一张 n 个点的带权无向图,点从 0~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]>=a[x,z]。

输出格式
输出一个整数,表示最短Hamilton路径的长度。

数据范围
$1 \le n \le20$
$0 \le a[i,j] \le 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

算法1

(暴力枚举) $O(n*n!)$

NP完全问题,相信纯暴力都可以写出,所以蒟蒻懒得写了

正解

正解思路(建议先看代码,不然有点难理解)
首先我们要思考如果让这个NP完全题目复杂度降低,那么可以优先考虑到使用位运算,状态压缩等解决思路。
然后接着思考,我们可以发现,我们所需要的不是整个方案,而只是方案最优解,所以我们只需要记录当前这个方案的最优解即可,那么我们考虑的状态,不久只有,在当前方案i中,目前抵达的点是j。
现在既然装填已经确定好了当前点j,那么这个j点是由哪一个状态移动而来的呢?我们可以选择k,也就是说我们的状态转移方程可以为

f[i][j]=min(f[i][j],f[i^(1<<j)][k]+weight[k][j]//感谢楼下大佬们指出打字错误.

以上转移方程,weight数组为权值 ,也就是weight[k][j]是k点到j点的权值
i^(1<<j)的意思是,i 异或 1右移j位,具体来说就是i这个方案集合 xor 10……0,(其中1的位置在第j位)。
那么这个位运算有什么用处呢,第一点它是在判断第j位的情况,第二点位运算处理速度很快。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int n,f[1<<20][21],i,j,k;
int weight[21][21];
int main()
{
    ios::sync_with_stdio(false);//加快cin的读入速度,但是scanf将会不能用。
    memset(f,0x3f,sizeof(f));//初始化最大值
    cin>>n;
    for (i=0; i<n; i++)
        for (j=0; j<n; j++)
            cin>>weight[i][j];
    f[1][0]=0;//第一个点是不需要任何费用的
    for (i=1; i<(1<<n); i++)//i代表着是一个方案集合,其中每一个位置1和0,代表着这个点经过还是没有经过
        for (j=0; j<n; j++)//枚举当前到了哪一个点
            if ((i>>j & 1))//如果i集合中第j位是1,也就是到达过这个点
                for (k=0; k<n; k++)//枚举到达j的点k
                    if ((i^(1<<j)) >> k & 1)//重点,判断k和j的条件,具体在上面解说
                        f[i][j]=min(f[i][j],f[i^(1<<j)][k]+weight[k][j]);//选择最小值,也就是判断,k点到j点最优,还是以前的方案最优
    cout<<f[(1<<n)-1][n-1];//输出最后的最优值
    return 0;
}

70 评论


用户头像
aiz   2023-04-05 23:28      1    踩      回复

这题不能用普利姆和克鲁斯卡尔吗

用户头像
丁真-珍珠   2024-04-20 14:50         踩      回复

我觉得可以,但这道题给的是矩阵形式的输入,要手动转成无向图的输入形式

用户头像
巩梓旭   2025-06-10 20:16 · 河北         踩      回复

不能,那样只是保证一条总路径最短的连通图。与题目要求从0点到n-1路径最短不一样,用克鲁斯卡尔得出来的连通图可能还要走回头路(一条路走多遍)才能从起始点0走到终点n-1。


用户头像
Keven11   2023-04-05 17:00      1    踩      回复

ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
(完整版)


用户头像
剑指Rejection   2019-11-28 21:08      1    踩      回复

谢谢您
但是我发现,把if ((i^(1<<j)) >> k & 1)这句话去掉也能AC
是因为数据水吗?还是这个判断就是不必要的?

用户头像
剑指Rejection   2019-11-28 21:30         踩      回复

下面把$i$看成是一个集合。这个判断应该等价于$k\in i$(从集合$i$中去掉城市$j$不影响$k\in i$的真假,除非$k=j$,但是这种情况不会影响对答案的优化)。那么把这个if去掉,就会导致满足$k\not \in i$的$k$参与答案优化。但是$f(\{x\},y)$这种状态是始终为无穷大的,归根到底也不会对答案有什么贡献,所以这个if是可以去掉的。各位大佬觉得呢……

用户头像
剑指Rejection   2019-11-28 21:33    回复了 剑指Rejection 的评论         踩      回复

弟弟mathjax,{}记号炸了。上面说的f(x,y)是f[{x}][y],其中x和y是两个不相同的城市。因为我们只对形如f[{a,b,c}][c]的状态进行更新,所以形如f[{x}][y],x!=y的状态始终是无穷大,不会影响答案。

用户头像
秦淮岸灯火阑珊   2019-11-30 18:13    回复了 剑指Rejection 的评论         踩      回复

您说的很对,因为考虑到本题目的最值性质,所以其实因为之前有过极值初始化,所以不需要考虑本问题,但是为了算法完整性,所以补上了这句话,

用户头像
剑指Rejection   2019-11-30 20:50    回复了 秦淮岸灯火阑珊 的评论         踩      回复

谢谢您
我学到了许多


用户头像
ʕʔ_18   2022-07-10 10:31         踩      回复

memset(f,0x3f,sizeof(f));//初始化最大值
为什么是0x3f?

用户头像
白井黑子   2022-07-10 11:54      1    踩      回复

按字节初始化,相当于0x3f3f3f3f

用户头像
ʕʔ_18   2022-07-10 15:00    回复了 白井黑子 的评论         踩      回复

谢谢

用户头像
雪下逢春   2023-05-25 02:05      1    踩      回复

按字节初始化,0x3f3f3f3f的好处有两点,一是这个数字足够大,二是这个数字可以做加法,避免用int -max造成数据溢出的情况


用户头像
WA声闹彻明   2022-06-19 00:44         踩      回复

请问这个条件我们能够获取到什么信息呢?或者说这题目少了这个条件是否还是这么做呢?
对于任意的 x,y,z,数据保证 a[x,y]+a[y,z]≥a[x,z]。

用户头像
Ice_spring   2022-07-02 14:22      2    踩      回复

不影响求解,在算法竞赛进阶指南这本书中直接就没有这个条件,一样的代码。满足该三角不等式条件的是一类特殊的哈密顿问题。

用户头像
WA声闹彻明   2022-07-04 16:45    回复了 Ice_spring 的评论         踩      回复

okok谢谢谢谢


用户头像
蹲在街角〆仰望晴天ゞ   2022-01-16 13:33         踩      回复

只能说tql,大佬


用户头像
Dsus4   2021-02-20 16:20         踩      回复

感谢大佬,终于懂了


用户头像
Taaa   2020-11-11 11:53         踩      回复

看了你的终于懂了


用户头像
mysql.apache   2020-07-04 13:06         踩      回复

为啥结果是[N-1]啊, 最后一步到其他的点不行吗

用户头像
ァ恋丄恶魇   2020-07-08 09:45         踩      回复

题目写了终点是n-1


用户头像
遍地跑小鸡   2020-06-29 22:24         踩      回复

想问一下,为什么循环时候是外层循环路径,内层循环终点的?如果反过来结论就是不对得了。这里我不是很理解,求大佬解答。

用户头像
yami_haha   2022-05-13 21:00         踩      回复

因为转移的时候需要用到的值总不能还未被更新过吧!


用户头像
Anoxia_3   2020-04-30 23:05         踩      回复

弱弱地问一句 纯暴力为啥是n*n! 起点固定不应该是n!吗,更具体点应该是(n-1)!

用户头像
云深不知处_5   2020-05-21 20:53         踩      回复

同问,我也在想为啥暴力 会多乘一个n

用户头像
垫底抽风   2020-08-28 09:54      2    踩      回复

爆搜枚举所有Hamilton路径 $O(n!)$ 的,每枚举到一种路径要 $O(n)$ 的算一下这个路径的长度,所以总的时间复杂度为 $O(n \times n!)$

用户头像
Anoxia_3   2020-08-28 11:22    回复了 垫底抽风 的评论         踩      回复

原来如此😁

用户头像
秦淮岸灯火阑珊   2020-08-29 08:51    回复了 垫底抽风 的评论      2    踩      回复

谢谢抽风

用户头像
ljy22222   2021-11-20 10:50    回复了 垫底抽风 的评论      1    踩      回复

谢谢懂了!


用户头像
FourTO   2020-04-16 00:11         踩      回复

想问一下题目中“其中第i行第j个整数表示点i到j的距离(记为a[i,j])”什么意思啊,题目就是找最短的方案能理解,这个题目 第 i 行 当中 第 j 个整数 表示 点 i 到 j 的距离,这个点 i ,j 从何来啊,希望大佬给解释下

用户头像
小呆呆   2020-04-26 17:11         踩      回复

题目给了一个矩阵,表示某些点到某些点的距离,例如a[i][j]指的是i号点到j号点的距离是a[i][j]

用户头像
小呆呆   2020-04-26 17:11         踩      回复

秦大佬暂时退役了

用户头像
秦淮岸灯火阑珊   2020-08-29 08:51    回复了 小呆呆 的评论         踩      回复

QwQ

用户头像
蹲在街角〆仰望晴天ゞ   2022-01-16 13:31    回复了 小呆呆 的评论         踩      回复

你是不是也是一个竞赛选手啊 ,感觉你也很强


用户头像
ARi_King   2019-11-26 18:40         踩      回复

秦同学大佬 这个既然是与floyd有关系 那么到哪个点不是最外层的循环

用户头像
秦淮岸灯火阑珊   2019-11-30 18:14         踩      回复

有关系,不代表很这类算法一模一样,他们有关系,是因为状压有一部分Floyd算法的思维.


用户头像
戈好雨   2019-10-01 15:23         踩      回复

同学用python怎么表示状态的变化呢?我尝试提前建立长度为2**n的二进制列表来表示状态,但这个创建时间太长了怎么办?

用户头像
秦淮岸灯火阑珊   2019-10-01 17:11         踩      回复

emm,我不会$python$,所以我也没有办法啊.

用户头像
福如东海   2019-10-24 17:08         踩      回复

python直接有set类型

用户头像
秦淮岸灯火阑珊   2019-10-25 19:30    回复了 福如东海 的评论         踩      回复

%%%


用户头像
开朗未来   2019-08-26 12:03         踩      回复

大佬我想问问为什么f[1][0]初始化为0,起点是0,那不应该是f[0][0]初始化为0吗

用户头像
秦淮岸灯火阑珊   2019-08-26 13:59         踩      回复

这里的$1$,是二进制下的$1$,也就是第$0$位为$1$,然后后面的$0$表示,上一次开始的点是$0$.
$f[i][j]$表示二进制状态为$i$,最后一次节点是$j$

用户头像
开朗未来   2019-08-27 15:29    回复了 秦淮岸灯火阑珊 的评论         踩      回复

谢谢,我把2的0次方当成0了

用户头像
秦淮岸灯火阑珊   2019-08-27 15:31    回复了 开朗未来 的评论         踩      回复

您客气了。


用户头像
鬼子进村   2019-08-14 09:06         踩      回复

倒数第五行判断那里 我写成 if(i^(1<<j)&1) 这样也过了。。。。就没有判断第k位莫名其妙的就过了。。

用户头像
秦淮岸灯火阑珊   2019-08-14 14:12         踩      回复

emm,我有点懵逼,是数据太水了吗?

用户头像
鬼子进村   2019-08-15 09:16    回复了 秦淮岸灯火阑珊 的评论         踩      回复

貌似 应该是吧

用户头像
希梦Cidream   2023-01-12 21:45    回复了 秦淮岸灯火阑珊 的评论         踩      回复

好像不是


用户头像
Sparks   2019-08-04 09:46         踩      回复

我觉得在举个例子更好,我理解了好半天,推个例子直接出来了

用户头像
秦淮岸灯火阑珊   2019-08-04 10:39      1    踩      回复

好的


用户头像
阿基米多多   2019-07-13 21:25         踩      回复

请问这和djikstra算法有什么不同?

用户头像
秦淮岸灯火阑珊   2019-07-13 22:13         踩      回复

dijskra是单源最短路径的算法,我们这个是基于Floyd算法,也就是多源最短路算法.


用户头像
robot_1   2019-05-30 21:25         踩      回复

谢谢您


用户头像
一定要刷完剑指offer   2019-05-11 19:47         踩      回复

大佬,这个题目用递归,然后回溯法优化怎么写呢?我发你个代码帮我看看

用户头像
秦淮岸灯火阑珊   2019-05-11 19:49         踩      回复

好的.


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息