当前位置:网站首页>最短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;
}
边栏推荐
- Fairygui joystick
- 基于rtklib源码进行片上移植的思路分享
- Remember an experience of ECS being blown up by passwords - closing a small black house, changing passwords, and changing ports
- HCIP Day 12
- In 2020, the average salary of IT industry exceeded 170000, ranking first
- Unity3d, Alibaba cloud server, platform configuration
- [leetcode19]删除链表中倒数第n个结点
- [offer29] sorted circular linked list
- What are the advantages of using SQL in Excel VBA
- Combination of fairygui check box and progress bar
猜你喜欢
Liste des boucles de l'interface graphique de défaillance
(core focus of software engineering review) Chapter V detailed design exercises
FairyGUI循環列錶
Fabrication of fairygui simple Backpack
[Chongqing Guangdong education] Shandong University College Physics reference materials
[算法] 剑指offer2 golang 面试题5:单词长度的最大乘积
Unity3D,阿里云服务器,平台配置
抗差估计在rtklib的pntpos函数(标准单点定位spp)中的c代码实现
idea问题记录
Vulnhub target: hacknos_ PLAYER V1.1
随机推荐
(1) Introduction Guide to R language - the first step of data analysis
Combination of fairygui check box and progress bar
抗差估计在rtklib的pntpos函数(标准单点定位spp)中的c代码实现
Teach you to release a DeNO module hand in hand
(5) Introduction to R language bioinformatics -- ORF and sequence analysis
By v$rman_ backup_ job_ Oracle "bug" caused by details
idea中好用的快捷键
Office提示您的许可证不是正版弹框解决
FairyGUI增益BUFF數值改變的顯示
[Yu Yue education] guide business reference materials of Wuxi Vocational and Technical College of Commerce
Programming homework: educational administration management system (C language)
How to reduce the shutdown time of InnoDB database?
[offer78]合并多个有序链表
KF UD分解之UD分解基础篇【1】
What are the advantages of using SQL in Excel VBA
[offer9] implement queues with two stacks
FairyGUI按钮动效的混用
微信小程序开发心得
[Offer18]删除链表的节点
GNSS定位精度指标计算