您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

算法竞赛进阶指南打卡系列 0x00 3.最短Hamilton路径

算法竞赛进阶指南打卡系列题解

0x00 3.最短Hamilton路径

  • 题目
    • 原题链接
    • 题面
  • 题解
    • 思路
    • 代码


题目

原题链接

AcWing 91. 最短Hamilton路径

题面

给定一张 n 个点的带权无向图,点从 0 ∼ n − 1 0∼n−1 0n1 标号,求起点 0 0 0 到终点 n − 1 n−1 n1 的最短 Hamilton 路径。

Hamilton 路径的定义是从 0 0 0 n − 1 n−1 n1 不重不漏地经过每个点恰好一次。

输入格式
第一行输入整数 n n 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 1n20
0 ≤ a [ i , j ] ≤ 1 0 7 0≤a[i,j]≤10^7 0a[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

题解

思路

暴力求解,即枚举n的全排列,之后求出最小值,其复杂度为 O ( n × n ! ) O(n×n!) O(n×n!) ,显然不可取。
本题的正解为 状态压缩DP ,时间复杂度为 O ( n 2 × 2 n ) O(n^2×2^n) O(n2×2n) ,思路如下:
在这里插入图片描述
其中DP数组的第一维表示经过的路径,我们可以用二进制数表示,其中倘若第 i i i 位为 0 0 0 表示未经过第 i i i 个点,为 1 1 1 表示经过第 i i i 个点,因此大小为 2 n 2^n 2n ,第二维为当前到达的点,因此大小为 n n n
对于 f [ i , j ] f[i, j] f[i,j] i i i 所表示的二进制数的第 j j j 位应该为 1 1 1 ,表示我们当前的路径一定是到达过第 j j j 个点的。
对于 f [ s , k ] f[s, k] f[s,k] ,由于我们会从 f [ s , k ] f[s, k] f[s,k] 转移至 f [ i , j ] f[i, j] f[i,j] ,即我们会从 k k k 点走到 i i i ,因此在 s s s 这个状态中的除了 j j j 这个点为 0 0 0 之外,其他的二进制位上的数应该和状态 i i i 一样,因此我们可得到 s = i − ( 1 < < j ) s = i -(1 << j) s=i(1<<j) ,当然此处的减法操作可以换为异或(^)操作。
由于涉及到 c++ 的 运算优先级 问题,特附此表(优先级 从大到小 ):

加减移位比较大小位与异或位或
+ , − +, - +, < < , > > <<, >> <<,>> > , < , = = , ! = >, <, ==, != >,<,==,!=&^|

代码

#include <bits/stdc++.h>

// #define int long long

#define x first
#define y second

using namespace std;

typedef long long LL;

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<vector<int>> w(n, vector<int>(n));
    for (int i = 0; i < n; i ++ ) {
        for (int j = 0; j < n; j ++ ) {
            cin >> w[i][j];
        }
    }

    vector<vector<int>> dp(1 << n, vector<int>(n, 1e9));
    dp[1][0] = 0;
    for (int i = 1; i < 1 << n; i ++ ) {
        for (int j = 0; j < n; j ++ ) {
            if (i >> j & 1) { // 判断状态i是否包含第j个点
                for (int k = 0; k < n; k ++ ) {
                    if ((i ^ 1 << j) >> k & 1) { // 判断转移过来的状态是否包含第k个点
                        dp[i][j] = min(dp[i][j], dp[i ^ 1 << j][k] + w[k][j]);
                    }
                }
            }
        }
    }

    cout << dp[(1 << n) - 1][n - 1] << "\n";

    return 0;
}

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进