哈密顿路径

超、凢脫俗 2022-03-06 07:18 183阅读 0赞

### 题意：给出邻接矩阵，最短Hamilton路径。（给定一张 n(n≤20) 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。） ###

### 分析：二进制状压dp，把i看做一个作一个n位二进制数，表示当前所有点的取或不取，dp【i】【j】代表子图i中当前点为j时的最短Hamilton距离，那么当前状态可能是这样转移的，从去掉j这个点的一个子图（在i图中）通过k点到达j点，那么dp【i】【j】 = min（dp【i】【j】，dp【 i^1<<j 】【k】+dis【k】【j】）。 ###

### 代码： ###

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int N = 1e7+10;
    const ll p = 1e9+7;
    int n,dp[1<<20][20],d[20][20];
    
    int main() {
        cin>>n;
        for(int i=0;i<(1<<n);i++)
            for(int j=0;j<n;j++)
                dp[i][j]=1e9;
        dp[1][0]=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                cin>>d[i][j];
        for(int i=1;i<(1<<n);i++) {
            for(int j=0;j<n;j++) {
                if((i>>j)&1) {
                    for(int k=0;k<n;k++) {
                        if((i>>k)&1) { ///分拣出每一位,通过k点来松弛
                            dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k]+d[k][j]);
                        }
                    }
                }
            }
        }
        cout<<dp[(1<<n)-1][n-1]<<endl;
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，183人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 2181哈密顿绕行世界问题（简单DFS）

哈密顿绕行世界问题 [HDU - 2181 ][HDU - 2181] include<cstdio> int a[20+

- 日理万妓/ 2024年02月17日 19:05/ 0 赞/ 60 阅读

相关第六章图论 6 AcWing 1615. 哈密顿回路

第六章图论 6 AcWing 1615. 哈密顿回路原题链接 [AcWing 1615. 哈密顿回路][AcWing 1615.] 思路根据哈密顿回路

左手的ㄟ右手/ 2023年09月24日 14:24/ 0 赞/ 42 阅读

相关回溯法-哈密尔顿回路

一、哈密顿回路哈密顿回路的定义： G=(V,E)是一个图，若G中一条路径通过且仅通过每一个顶点一次，称这条路径为哈密顿路径。若G中一个回路通过且仅通过每一个顶点一次，称

野性酷女/ 2022年11月18日 04:48/ 0 赞/ 139 阅读

相关 JavaScript实现hamiltonianCycle哈密尔顿图算法（附完整源码）

JavaScript实现hamiltonianCycle哈密尔顿图算法（附完整源码） Comparator.js完整源代码 LinkedListNode.js

﹏ヽ暗。殇╰゛Y/ 2022年09月07日 03:47/ 0 赞/ 171 阅读

相关 C - 哈密顿绕行世界问题——DFS

Think: 1DFS: 1>控制结束条件 2>传递 2反思: 1>不自信 2>未判断最后一个城市是否可以到达初始出发城市（感谢鑫哥点拨） 3收获:

超、凢脫俗/ 2022年06月15日 04:16/ 0 赞/ 120 阅读

相关欧拉图和哈密顿图

欧拉图及欧拉路径欧拉图如果图G上有一条经过所有顶点、所有边的闭路径（边不重复，顶点可以重复）充分必要条件

客官°小女子只卖身不卖艺/ 2022年05月27日 13:14/ 0 赞/ 208 阅读

相关哈密顿路径

这个“哈密瓜路径”网上查了好久没搞明白，我这个的代码无奈定义了4个节点和5条边，将就混过课程设计课。放代码和结果从我做起！欢迎大家留言！ 1. 问题描述在图G中找

柔情只为你懂/ 2022年03月28日 10:36/ 0 赞/ 202 阅读

相关 (PAT 1122) Hamiltonian Cycle (哈密顿图)

The "Hamilton cycle problem" is to find a simple cycle that contains every vertex in a g

偏执的太偏执、/ 2022年03月20日 11:58/ 0 赞/ 194 阅读

相关哈密顿路径

题意：给出邻接矩阵，最短Hamilton路径。（给定一张 n(n≤20) 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。

超、凢脫俗/ 2022年03月06日 07:18/ 0 赞/ 184 阅读

相关 HDU-2181 哈密顿绕行世界问题（dfs）

Problem Description: 一个规则的实心十二面体，它的 20个顶点标出世界著名的20个城市，你从一个城市出发经过每个城市刚好一次后回到出发的城市。 Inpu

野性酷女/ 2022年02月13日 08:57/ 0 赞/ 175 阅读