题解 | #dd爱探险#

带权有向完全图的受限哈密顿路径

1. 问题分析

本问题本质上是一个非对称旅行商问题（TSP）的变体。我们需要在包含 个节点的有向完全带权图中，寻找一条能够遍历所有节点的路径（即哈密顿路径），使得总代价最小。

关键约束点分析：

• 规模约束：。这是一个极其强烈的信号，暗示算法复杂度应为指数级，通常指向 状态压缩动态规划（State Compression DP），复杂度约为 。
• 路径性质：需要进行 次跳跃，这意味着路径不回到起点（是非闭合的路径，而非回路）。起点任意，终点任意，必须恰好经过每个节点一次。
• 特殊能力约束：
  • 必须恰好有一次跳跃代价归零（）。
  • 必须恰好有一次跳跃代价翻倍（）。
  • 其余 次跳跃为原始代价（）。
• 独立性：题目描述“另一次跳跃”，隐含这两次特殊操作必须发生在不同的边上。对于 的最小情况，仅有 2 次跳跃，这也意味着两次跳跃分别承担了 和 的效果。

2. 核心算法：多维状态压缩动态规划

由于 很小，且涉及到集合状态（哪些节点已访问）以及额外的状态标记（特殊能力是否已使用），最合适的架构是状态压缩 DP。

2.1 状态定义

我们需要定义一个多维数组 DP 来描述当前决策过程中的所有必要信息：

• mask (位掩码): 一个整数，二进制表示集合 中哪些空间站已经被访问过。如果第 位为 1，则表示空间站 已在路径中。
• u (当前节点): 最近一次访问的空间站编号（路径的末端），用于计算前往下一个节点的代价 。
• used_zero (布尔值/0-1): 标记是否已经使用了“重力加速”（代价归零）。0 表示未使用，1 表示已使用。
• used_double (布尔值/0-1): 标记是否已经使用了“反重力加速”（代价翻倍）。0 表示未使用，1 表示已使用。

DP 值的含义： DP[mask][u][z][d] 表示在访问状态为 mask，当前停留在节点 u，且特殊能力使用状态为 z 和 d 时，所产生的最小累积代价。

2.2 状态转移方程

假设当前状态为 DP[mask][u][z][d]，我们要尝试跳跃到下一个未访问的节点 （即 mask 的第 位为 0）。 设 。我们将产生三个分支决策：

1. 普通跳跃：不使用任何特殊能力。

   • 条件：无限制（但这会保留 和 的状态不变，题目要求最终必须都用，所以非强制，但在中间过程中是允许的）。
   • 转移：

2. 使用重力加速（）：

   • 条件：当前 （尚未归零过）。
   • 转移：

3. 使用反重力加速（）：

   • 条件：当前 （尚未翻倍过）。
   • 转移：

3. 复杂度分析

3.1 时间复杂度

算法主要由嵌套循环构成：

• 状态空间大小：。
• 每个状态的转移次数：（尝试所有可能的下一个节点 ）。

总时间复杂度为：

3.2 空间复杂度

需要存储 DP 数组：

• 个整数。
• 若使用 32 位整数 (4 Bytes)，内存约为 16 MB。
• 这远低于通常的内存限制（128MB 或 256MB）。

4. 代码实现

#include <bits/stdc++.h>
#include <limits>
using namespace std;
using ll = long long;

static constexpr int INF = 0x3f3f3f3f;

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

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

    // dp[mask][current_node][used_zero][used_double]
    vector<vector<vector<vector<int>>>> dp((1 << n), vector<vector<vector<int>>>(n,
                                           vector<vector<int>>(2, vector<int>(2, INF))));

    for (int i = 0; i < n; i++) {
        dp[1 << i][i][0][0] = 0;
    }

    for (int mask = 1; mask < (1 << n); mask++) {
        for (int u = 0; u < n; u++) {
            if (((mask >> u) & 1) == 0)
                continue;
            for (int z = 0; z < 2; z++) {
                for (int d = 0; d < 2; d++) {
                    if (dp[mask][u][z][d] == INF)
                        continue;
                    for (int v = 0; v < n; v++) {
                        if ((mask >> v) & 1)
                            continue;
                        int next_mask = mask | (1 << v);
                        int cost = p[u][v];

                        // Option 1: Normal jump (if we haven't finished the path or need to save abilities)
                        if (dp[next_mask][v][z][d] > dp[mask][u][z][d] + cost) {
                            dp[next_mask][v][z][d] = dp[mask][u][z][d] + cost;
                        }

                        // Option 2: Gravity Acceleration (Cost becomes 0)
                        if (z == 0) {
                            if (dp[next_mask][v][1][d] > dp[mask][u][z][d]) {
                                dp[next_mask][v][1][d] = dp[mask][u][z][d];
                            }
                        }

                        // Option 2: Gravity Acceleration (Cost becomes 0)
                        if (d == 0) {
                            if (dp[next_mask][v][z][1] > dp[mask][u][z][d] + cost * 2) {
                                dp[next_mask][v][z][1] = dp[mask][u][z][d] + cost * 2;
                            }
                        }
                    }
                }
            }
        }
    }

    int ans = INF;
    int final_mask = (1 << n) - 1;
    for (int i = 0; i < n; i++) {
        ans = min(ans, dp[final_mask][i][1][1]);
    }

    cout << ans << endl;

    return 0;
}