382 字
2 分钟
状压 DP 求解哈密顿路径 (Hamiltonian Path)

状压 DP 求解哈密顿路径 (Hamiltonian Path)#

1. 核心原理#

哈密顿路径是经过图中每个顶点恰好一次的路径。该问题为 NP-Hard,在竞赛中顶点数通常较小(n≤20n \le 20),标准解法为状态压缩动态规划。

2. 状态设计与转移#

  • 状态表示:dp(mask,u)dp(mask, u) 表示当前经过的节点集合为二进制掩码 maskmask、当前停留在节点 uu 的方案数或最短路径长度。
  • 状态转移:枚举 uu 的出边 (u,v)(u, v),若 vv 不在集合中(即 (mask&(1≪v))==0(mask \& (1 \ll v)) == 0): dp(mask∣(1≪v),v)=(dp(mask∣(1≪v),v)+dp(mask,u)) mod MODdp(mask \mid (1 \ll v), v) = (dp(mask \mid (1 \ll v), v) + dp(mask, u)) \bmod MOD
  • 时间复杂度:O(2n⋅n2)O(2^n \cdot n^2),空间复杂度:O(2n⋅n)O(2^n \cdot n)。

3. 实战模板代码 (CSES Hamiltonian Flights)#

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int n, m;
vector<int> adj[21];
int dp[1 << 20][20];
int main() {
ios::sync_with_stdio(0);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
--u;
--v;
adj[u].push_back(v);
}
dp[1][0] = 1; // 从起点 0 开始,集合为 {0} (mask = 1)
for (int mask = 1; mask < (1 << n); mask++) {
// 剪枝:若终点 n-1 提前被访问且未走完所有点,跳过
if ((mask & (1 << (n - 1))) && mask != (1 << n) - 1)
continue;
for (int u = 0; u < n; u++) {
if (!dp[mask][u])
continue;
for (int v : adj[u]) {
if (!(mask & (1 << v))) {
int next_mask = mask | (1 << v);
dp[next_mask][v] = (dp[next_mask][v] + dp[mask][u]) % MOD;
}
}
}
}
cout << dp[(1 << n) - 1][n - 1] << '
'; return 0;
}
状压 DP 求解哈密顿路径 (Hamiltonian Path)
https://sanzenin.top/posts/obsidian/哈密顿路径/
作者
Sanzenin 凪
发布于
2026-09-03
许可协议
CC BY-NC-SA 4.0

分享文章

生成精美分享图或复制链接,与更多人分享本文。

继续阅读

沿着主题读

基于共同的标签与分类

换条路线

从其他文章中稳定抽取