382 字
2 分钟
状压 DP 求解哈密顿路径 (Hamiltonian Path)
状压 DP 求解哈密顿路径 (Hamiltonian Path)
1. 核心原理
哈密顿路径是经过图中每个顶点恰好一次的路径。该问题为 NP-Hard,在竞赛中顶点数通常较小(),标准解法为状态压缩动态规划。
2. 状态设计与转移
- 状态表示: 表示当前经过的节点集合为二进制掩码 、当前停留在节点 的方案数或最短路径长度。
- 状态转移:枚举 的出边 ,若 不在集合中(即 ):
- 时间复杂度:,空间复杂度:。
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/哈密顿路径/分享文章
生成精美分享图或复制链接,与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ,距今已过 74 天
部分内容可能已过时