洛谷P1171 售货员的难题 题解 & 旅行商问题（TSP 问题）模板

题目链接：P1171 售货员的难题

题目描述：

某乡有 \(n\) 个村庄，有一个旅行商 qry，他要到各个村庄去售货。

各村庄之间的路程 \(e(i,j)\) 是已知的，且 \(A\) 村到 \(B\) 村与 \(B\) 村到 \(A\) 村的路大多不同（有向图）。

为了提高效率，qry 从商店出发到每个村庄一次，然后返回商店所在的村。

假设商店所在的村庄为 \(1\)，他不知道选择什么样的路线才能使所走的路程最短。

请你帮他选择一条最短的路。

输入格式：

第一行是一个整数，表示村庄数 \(n\)。

接下来 \(n\) 行，每行 \(n\) 个整数，第 \(i\) 行的第 \(j\) 个整数表示 \(i\) 到 \(j\) 的单向路径的距离 \(e(i,j)\)。

输出格式：

一行一个整数表示最短的路程。

数据范围：

保证 \(2 \leq n \leq 20,~1 \leq e(i,j) < 10^3,~e(i,i) = 0\)。

考虑状压dp。方便起见，把节点记为 \(0\) 到 \(n-1\) ，而不是 \(1\) 到 \(n\) 。

记 \(f(S,i)\) 为当前走到 \(i\) ，已经走过了 \(S\) 集合中的点时的最小哈密顿路径长。

这里最小哈密顿路径 就是经过每个节点恰好一次的、总长最短的路径。

初始值 \(f(\{0\},0)=0\) ，即从 \(0\) 出发走过了 \(0\) 的花费，当然为 \(0\) 。

注意旅行商还要回来，答案就是 \(\displaystyle \min_{0 \le i \le n - 1} (f(U,i)+ e(i,0))\) ，其中 \(U\) 为全集。

考虑转移，每轮枚举 \(i\,(i \in S)\) ，有 \[ f(S,i) \gets \min_{(j \ne i) \land (j \in S)}\left(f(S,i), \,f(S\setminus\{i\},j) + e(j,i)\right) \] 直接转移即可，时间复杂度 \(O(n^2\cdot2^n)\)

代码：（循环rep(S, 2, U) 内，注释部分的写法常数较大，没注释的常数较小不过略难理解）

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1 << 20) + 5)

int n, e[N][22]; ll f[N][22];
int lowbit(int x) { return x & (-x); }
// 定义的 ctz(x) 当 x > 0 返回 x 右侧 0 的个数，比如 ctz(8) = 3 ，因为 8 = (1000)_2
#define ctz(x) __builtin_ctz(x)
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; const int U = (1 << n) - 1;
    rep(i, 0, n - 1) rep(j, 0, n - 1) cin >> e[i][j];
    memset(f, 0x3f, sizeof(f)); f[1][0] = 0;
    rep(S, 2, U)
    {   
        // rep(i, 0, n - 1) if((S >> i) & 1)
        //     rep(j, 0, n - 1) if(j != i && ((S >> j) & 1))
        //         down(f[S][i], f[S ^ (1 << i)][j] + e[j][i]);
        for(int x = S; x > 0; x -= lowbit(x))
            for(int y = S; y > 0; y -= lowbit(y))
            {
                const int i = ctz(x), j = ctz(y);
                if(i != j) down(f[S][i], f[S ^ (1 << i)][j] + e[j][i]);
            }
    }
    ll res = INF;
    rep(i, 0, n - 1) down(res, f[U][i] + e[i][0]);
    cout << res << '\n';
    return 0;
}