最短Hamilton路径
题意
给定一张 n 个点的带权无向图，点从 0∼n−1 标号，求起点 0 到终点 n−1 的最短 Hamilton 路径。
Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。
思路：
将每个点的状态用一个二进制整数 i 表示，i的第 k 位为 1 表示经过了第 k 个点，否则表示还没经过第 k 个点
然后用 j 表示当前状态下最后一个经过的点的编号，f[i][j] 表示 当前经过的点的状态为 i 最后一个经过的点为 j 的最短路径
那么我们要求的就是 f[(1 << n) - 1][n - 1] 即点 0~n-1 都经过，且最后经过的点为 n-1 的最短路径
因为每一个点只能被经过一次，那么j 一定是刚刚经过的，所以上一步的状态是 i ^ (1 << j) 即 i的第 j 位为 0 。另外，上一时刻所在的点可能是 i ^ (1 << j) 中任何一个为1 的点 k 所以可以考虑
所有满足((i ^ (1 << j) >> k) & 1 的点，求 f[((i ^ (1 << j) >> k) & 1][k] + w[k][j] 的最小值即可
代码
#include<bits/stdc++.h> // #define int long long #define INF 0x3f3f3f3f #define mod 1000000007 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) using namespace std; typedef long long LL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } const int N = 1e5 + 10; int n; int f[1 << 20][20]; // i - 当前状态 j - 最后经过的点为j点 int w[20][20]; void solve() { cin >> n; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cin >> w[i][j]; } } memset(f, 0x3f, sizeof f); f[1][0] = 0; for (int i = 0; i < (1 << 20); ++i) { // 当前路径的状态 1表示经过 0表示未经过 for (int j = 0; j < n; ++j) { // 当前走到了哪个点 if ((i >> j) & 1) { for (int k = 0; k < n; ++k) { // 上一步走到了哪个点 if ((i ^ (1 << j)) & (1 << k)) { f[i][j] = min(f[i][j], f[i ^ (1 << j)][k] + w[k][j]); } } } } } cout << f[(1 << n) - 1][n - 1] << endl; } signed main() { // int t; cin >> t; // while (t--) solve(); return 0; }
