link
不会状压，遂看蓝书。

二进制状态压缩操作

状压 DP 浅学

状态压缩就是将所有节点的状态（0 或 1，表示选或者不选）按顺序组合成一个二进制数，然后枚举这个二进制数所代表的十进制数，以枚举状态。实质是对状态和代码的优化。
举例

// 优化前
int f[2][2][2][2][2][n];
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)

rep (i, 0, 1) rep (j, 0, 1) rep (k, 0, 1) rep (l, 0, 1)  rep (m, 0, 1)
rep (i, 1, n) {
    // 状态转移...
}

// 优化后
int f[1 << n][n]
rep (i, 0, (1 << n) - 1)
    rep (j, 1, n) {
        // 状态转移...
    }

正文

设 $f_{i, j}$ 表示每个节点经过状态为 i 且目前在 j 点的最短 Hamilton 路径，其中 i 为一个 n 位二进制数。

f_{i, j} = \min\{f_{i \oplus 2^j, k} + weight_{k, j}\}$$，其中 $k \in [0, n)$，且仅当 i 在二进制表示下的第 k 位为 1 时可转移。 初值：$f_{1, 0} = 0$ 表示只经过点 0 且最短 Hamilton 路径长度为 0，因为没有其他点被经过。 目标：$f_{2^n - 1, n - 1}$ 题目要求为求 0 ~ n - 1 的最短 Hamilton 路径，因此最后一个经过的点为 n - 1。 时间复杂度：$\mathrm{O} (n^2 \cdot 2^n)$ ### 实现 ```cpp #include <bits/stdc++.h> using ll = long long; constexpr ll inf = 1e18; auto main()->int { std::cin.tie(nullptr)->sync_with_stdio(false); int n; std::cin >> n; std::vector<std::vector<ll>> a(n, std::vector<ll>(n, 0)); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { std::cin >> a[i][j]; } } std::vector<std::vector<ll>> h(1 << n, std::vector<ll>(n, inf)); h[1][0] = 0; for (int i = 1; i < (1 << n); ++i) { // 遍历状态 for (int j = 0; j < n; ++j) { // 枚举当前经过的点 j if (i >> j & 1) { // 由于 j 正在被经过，因此当前经过状态中点 j 的状态必定为 1（决策 1） for (int k = 0; k < n; ++k) { // 枚举上一时刻所处的点 k if ((i ^ 1 << j) >> k & 1) { // 决策 2 // 由于 j 正在被经过，因此上一个经过状态中点 j 的状态必定为 0 // i xor 1 表示上一个状态 h[i][j] = std::min(h[i][j], h[i ^ 1 << j][k] + a[k][j]); // 状态转移 } } } } } std::cout << h[(1 << n) - 1][n - 1]; return 0; } ```