汉密尔顿回路与路径 (Hamiltonian Cycle & Path)¶

汉密尔顿路径 (Hamiltonian Path)：经过图中每个顶点恰好一次的路径。
汉密尔顿回路 (Hamiltonian Cycle)：起点与终点相同，且除起点外经过每个顶点恰好一次的回路。

不同于可以在 \(\mathcal{O}(V + E)\) 判定的欧拉回路，判定一般图中是否存在汉密尔顿回路是一个著名的 NP-完全问题 (NP-Complete)。

经典充分性判定定理¶

对于包含 \(n \ge 3\) 个顶点的无向简单图：

狄拉克定理 (Dirac's Theorem)：若对图中任意顶点 \(u\)，均有其度数 \(\deg(u) \ge \lceil n / 2 \rceil\)，则图一定存在汉密尔顿回路。
奥尔定理 (Ore's Theorem)：若对图中任意一对不相邻的顶点 \(u, v\)，均满足 \(\deg(u) + \deg(v) \ge n\)，则图一定存在汉密尔顿回路。

状态压缩动态规划求解 (TSP / 最短汉密尔顿回路)¶

在算法竞赛中，当 \(n \le 20 \sim 22\) 时，通常采用状态压缩 DP (Bitmask DP) 求解最短汉密尔顿路径或回路（旅行商问题，TSP）。

设二进制掩码 \(mask \in [1, 2^n - 1]\) 表示已访问顶点的集合（第 \(i\) 位为 \(1\) 表示点 \(i\) 已访问）。
定义 \(dp[mask][u]\) 表示当前已走过的节点集合为 \(mask\)，且当前停留在节点 \(u\) 时的最小路径权值。
状态转移方程：

\[ dp[mask \mid (1 \ll v)][v] = \min \big( dp[mask \mid (1 \ll v)][v],\; dp[mask][u] + \text{weight}(u, v) \big) \]

时间复杂度：\(\mathcal{O}(2^n \cdot n^2)\)，空间复杂度：\(\mathcal{O}(2^n \cdot n)\)。

#include <vector>
#include <algorithm>

constexpr long long INF = 0x3f3f3f3f3f3f3f3fLL;

// dist[u][v] 为 u 到 v 的有向边权 (不存在边设为 INF)
// 返回从起点 0 出发，遍历所有节点恰好一次的最短路径长度
long long hamiltonian_path(int n, const std::vector<std::vector<long long>> &dist) {
    int total_states = 1 << n;
    std::vector<std::vector<long long>> dp(total_states, std::vector<long long>(n, INF));

    dp[1][0] = 0; // 起点为 0，初始状态仅包含点 0 (掩码二进制 00...001)

    for (int mask = 1; mask < total_states; ++mask) {
        for (int u = 0; u < n; ++u) {
            if (dp[mask][u] == INF) continue;

            // 枚举下一个前往的顶点 v
            for (int v = 0; v < n; ++v) {
                if (!(mask & (1 << v)) && dist[u][v] != INF) {
                    int next_mask = mask | (1 << v);
                    dp[next_mask][v] = std::min(dp[next_mask][v], dp[mask][u] + dist[u][v]);
                }
            }
        }
    }

    // 求访问完所有点 (mask == (1 << n) - 1) 的最短路径
    long long ans = INF;
    for (int u = 0; u < n; ++u) {
        ans = std::min(ans, dp[total_states - 1][u]);
    }
    return ans;
}

// 求解汉密尔顿回路 (最后回到起点 0)
long long tsp_cycle(int n, const std::vector<std::vector<long long>> &dist) {
    int total_states = 1 << n;
    std::vector<std::vector<long long>> dp(total_states, std::vector<long long>(n, INF));
    dp[1][0] = 0;

    for (int mask = 1; mask < total_states; ++mask) {
        for (int u = 0; u < n; ++u) {
            if (dp[mask][u] == INF) continue;
            for (int v = 0; v < n; ++v) {
                if (!(mask & (1 << v)) && dist[u][v] != INF) {
                    dp[mask | (1 << v)][v] = std::min(dp[mask | (1 << v)][v], dp[mask][u] + dist[u][v]);
                }
            }
        }
    }

    long long min_cycle = INF;
    for (int u = 1; u < n; ++u) {
        if (dp[total_states - 1][u] != INF && dist[u][0] != INF) {
            min_cycle = std::min(min_cycle, dp[total_states - 1][u] + dist[u][0]);
        }
    }
    return min_cycle;
}