当前位置:网站首页>最短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;
}
边栏推荐
- Esp8266 connect onenet (old mqtt mode)
- FairyGUI条子家族(滚动条,滑动条,进度条)
- How to add music playback function to Arduino project
- isEmpty 和 isBlank 的用法区别
- Fairygui joystick
- FairyGUI复选框与进度条的组合使用
- 1041 be unique (20 points (s)) (hash: find the first number that occurs once)
- 【干货】提升RTK模糊度固定率的建议之周跳探测
- NRF24L01 troubleshooting
- Itext 7 生成PDF总结
猜你喜欢
Theoretical derivation of support vector machine
What are the advantages of using SQL in Excel VBA
Matlab读取GNSS 观测值o文件代码示例
(4) Data visualization of R language -- matrix chart, histogram, pie chart, scatter chart, linear regression and strip chart
Unity3D,阿里云服务器,平台配置
Mysql database reports an error: row size too large (> 8126) Changing some columns to TEXT or BLOB or using ROW_ FORMAT=DY
Unity3d, Alibaba cloud server, platform configuration
Combination of fairygui check box and progress bar
Affichage du changement de valeur du Buff de gain de l'interface graphique de défaillance
(core focus of software engineering review) Chapter V detailed design exercises
随机推荐
Remember an experience of ECS being blown up by passwords - closing a small black house, changing passwords, and changing ports
【rtklib】在rtk下使用抗差自适应卡尔曼滤波初步实践
[Offer29] 排序的循环链表
Unity3D基础入门之粒子系统(属性介绍+火焰粒子系统案例制作)
Detailed explanation of truncate usage
Gravure sans fil Bluetooth sur micro - ordinateur à puce unique
[Chongqing Guangdong education] reference materials for regional analysis and planning of Pingdingshan University
Design and implementation of general interface open platform - (39) simple and crude implementation of API services
2021.11.10 compilation examination
使用rtknavi进行RT-PPP测试
Programming homework: educational administration management system (C language)
Comparative analysis of the execution efficiency of MySQL 5.7 statistical table records
Unity scene jump and exit
FGUI工程打包发布&导入Unity&将UI显示出来的方式
Itext 7 生成PDF总结
What are the functions and features of helm or terrain
JUC forkjoin and completable future
音乐播放(Toggle && PlayerPrefs)
How to reduce the shutdown time of InnoDB database?
Minio file download problem - inputstream:closed