当前位置:网站首页>最短Hamilton路径 (状压DP)
最短Hamilton路径 (状压DP)
2022-07-06 09:18:00 【小陈同学_】
题目
给定一张 n n n 个点的带权无向图,点从 0 ∼ n − 1 0∼n−1 0∼n−1 标号,求起点 0 0 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 n 个整数,其中第 i i i 行第 j j j 个整数表示点 i i i 到 j j j 的距离(记为 a [ i , j ] a[i,j] a[i,j])。
对于任意的 x , y , z x,y,z x,y,z,数据保证 a [ x , x ] = 0 a[x,x]=0 a[x,x]=0, a [ x , y ] = a [ y , x ] a[x,y]=a[y,x] a[x,y]=a[y,x] 并且 a [ x , y ] + a [ y , z ] ≥ a [ x , z ] a[x,y]+a[y,z]≥a[x,z] a[x,y]+a[y,z]≥a[x,z]。
输出格式
输出一个整数,表示最短 Hamilton 路径的长度。
数据范围
1 ≤ n ≤ 20 1≤n≤20 1≤n≤20
0 ≤ a [ i , j ] ≤ 1 0 7 0≤a[i,j]≤10^7 0≤a[i,j]≤107
输入样例:
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
f [ i ] [ j ] : f [ i ] [ j ] 表 示 从 0 走 到 j , 走 过 的 所 有 点 是 i 的 所 有 路 径 f[i][j]:f[i][j]表示从0走到j,走过的所有点是i的所有路径 f[i][j]:f[i][j]表示从0走到j,走过的所有点是i的所有路径
1.根据上面状态的含义,我们就会很好想了
2.既然每个f[i][j]表示的是从0走到j,走到的所有点是i的路径,集合划分该怎么划分呢?
3.依据找每个方案的最后一个不同点,我们可以发现每个点是可以由其他点走过来的
4.如果我们从某一个点k走到点j,那么我们当前状态是不包含j的,因为还没有走到j
5.根据4可以得出f[i][j]可以由f[i-(j)][k]+g[j][k]。说明 (j):j这个点的二进制表示,g[j][k]:j走到k的距离
6.根据状态定义:初始化f为负无穷——————————f[1][0]=0:(0走到自己的距离肯定为0)
7.最后答案为走到n-1号点,并且所有点都走过:f[(1<<n)-1][n-1]
AC代码(C++)
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=20,M=1<<N;
int f[M][N]; //f[i][j]表示从0走到j,走过的所有点是i的所有路径 例:i=110011(0代表没有走过,1代表走过,并且最右边的是0这个点)
int n;
int w[N][N]; //w[i][j]表示i到j这个点的距离
int main(){
scanf("%d",&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=0;i<1<<n;i++){
//枚举点的所有状态
for(int j=0;j<n;j++){
//枚举点的个数
if(i>>j&1){
//i>>j:求i的第j位数字. 如果&1成立,则代表j这个点已经走过
for(int k=0;k<n;k++){
//k->j
if(i>>k&1 && j!=k){
//跟上边的判断一样, 表示k这个点走过并且不是自己
f[i][j]=min(f[i][j],f[i-(1<<j)][k]+w[k][j]); //判断本方案最优还是从i->k,再从k->j最优
}
}
}
}
}
printf("%d",f[(1<<n)-1][n-1]); //最优解
return 0;
}
边栏推荐
- 1041 Be Unique (20 point(s))(哈希:找第一个出现一次的数)
- Vulnhub target: hacknos_ PLAYER V1.1
- [算法] 剑指offer2 golang 面试题4:只出现一次的数字
- PR 2021 quick start tutorial, first understanding the Premiere Pro working interface
- Flink late data processing (3)
- Get the position of the nth occurrence of the string
- What is the maximum length of MySQL varchar field
- First use of dosbox
- Fairygui loop list
- RTKLIB: demo5 b34f.1 vs b33
猜你喜欢
音乐播放(Toggle && PlayerPrefs)
Mysql database reports an error: row size too large (> 8126) Changing some columns to TEXT or BLOB or using ROW_ FORMAT=DY
平衡二叉树详解 通俗易懂
Conditional probability
Fabrication of fairygui simple Backpack
ORA-02030: can only select from fixed tables/views
idea中导包方法
341. Flatten nested list iterator
NovAtel 板卡OEM617D配置步骤记录
[Chongqing Guangdong education] Shandong University College Physics reference materials
随机推荐
【GNSS数据处理】赫尔默特(helmert)方差分量估计解析及代码实现
Special palindromes of daily practice of Blue Bridge Cup
Unity3D,阿里云服务器,平台配置
ORA-02030: can only select from fixed tables/views
Agile development helps me
Unity3D基础入门之粒子系统(属性介绍+火焰粒子系统案例制作)
Fairygui loop list
Theoretical derivation of support vector machine
[899] ordered queue
Unity3D制作注册登录界面,并实现场景跳转
Meanings and differences of PV, UV, IP, VV, CV
Expected value (EV)
Game 280 weekly
There is no red exclamation mark after SVN update
How to improve the deletion speed of sequential class containers?
[算法] 剑指offer2 golang 面试题13:二维子矩阵的数字之和
PRIDE-PPPAR源码解析
What is the maximum length of MySQL varchar field
2021.11.10汇编考试
單片機藍牙無線燒錄