91. 最短Hamilton路径
题目描述
给定一张 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≤n≤20
0≤a[i,j]≤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
本蒟蒻第一次写题解,这道题困惑了我很久,希望这篇题解可以帮到你。如果有不对的,请大牛指出!(不喜勿喷呐!!!)
首先,我们先引入一个概念,就是状态压缩,这种题的核心。
举个栗子:
8化为二进制就是1000,这个1000就可以表示走过第4个点(从右往左看,第4位是1),而第1,2,3个点没有走过(从左往右看,第1,2,3位是零)。
从这个栗子我们可以看到,一个十进制的数转为二进制就可以表示一个状态(即走过那些点)
第二,这道题的本质就是给定一个无向图,求0点到n-1点的最短Hamilton路径(全部走完),所以起点(0点)和终点(n-1点)已经完全固定。
那么,我们完全可以假定一个点作为次终点。题目就转化为了求0点到这个假定终点的最短Hamilton路径(因为次终点到终点的距离已经固定)
第三,开始推转移方程。
先定义dp[i][j]的含义,我的定义是第i种走法(用状态压缩,即这个数字表示的情况,走过那些点),j为终点的最短Hamilton路径。
那么假设我选择的次终点的点为k点,那么就有转移方程dp[i][j]=min(dp[i][j],dp[i-(1<<j)][k]+lj[k][j]);
首先求最小值,min就不用说了吧。
然后,i-(1<<j)的含义:i表示目前的所有情况,因为j是终点,又不能重复走,所以我们需要把i状态中,代表j这个点的位改成0(即表示不走j),这样我们就可以排除j的情况了,那么最小路径就是0到k的最小路径加上k到j的路径了。
那么我们就只用一个循环i表示情况,一个循环j表示终点,一个循环k表示次终点,逐渐dp,就可以得出最终答案了。
特殊说明:为什么把i状态中,代表j这个点的位改成1,用的是“-”呢?这是因为执行这个之前需要判断i>>j&1
这表示i中j在情况内(即代表j这个点的位数是1)才为真,所以在i情况中代表j这个点的位上的数字必定是1(才能执行到这步)
AC代码~
#include<bits/stdc++.h>//万能头不用我说了吧?
using namespace std;
const int N=20,M=1<<N;//1<<n代表2^n
int lj[N][N],dp[M][N];//lj数组储存路径的长度
int main()
{
int n;
cin>>n;//朴素的输入~
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>lj[i][j];//华丽的输入~
memset(dp,0x3f,sizeof(dp));//因为求最小值,所以赋最大值
dp[1][0]=0;//0走到0当然是0啦~
for(int i=0;i<1<<n;i++)
for(int j=0;j<n;j++)
if(i>>j&1)//判断i情况中j这个点是否走过,如果走过,就可以选作终点来dp
for(int k=0;k<n;k++)
if(i>>k&1)//判断i情况中k这个点是否走过,如果走过,才可以作为中转站(次终点)来dp
dp[i][j]=min(dp[i][j],dp[i-(1<<j)][k]+lj[k][j]);//华丽的转移方程~
cout<<dp[(1<<n)-1][n-1]<<endl;//为什么是(1<<n)-1,见附1
return 0;//华丽的结束(啊~终于快完了)~
}
附1
关于为什么最后输出是(1<<n)-1,小编也不知道
最终我们要的结果中,必须全部都走过,也就是11..11(n个1)的二进制所表示的状态。
1<<n所表示的是100..00(n个0),所以需要-1才能表示所有点都走过的情况(i)
%%%%%%%%%%%%%%%%%+++%%%%%%%%%%
+