TSP的状压dp写法

zzk2010 · 2023-07-17 15:09:00 · 算法·理论

周赛打的跟个纸张一样，T6 模数 1e10+7 写成 1e9+7 痛失 90pts ，T5 想到 TSP 问题却不会写，提前退役得了。

AT 和 CF Rating 与校内比赛成绩成反比，而且都很拉。

原问题

从一个点出发，不重不漏经过所有 n 个点后回到起点，求最短线路。

• n \le 15

没有多项式时间复杂度解法，但由于点很少，可以状压。

首先，最后一个点是 to 的话，先把 to 这个点加进点集中，则newstate = state ~|~ (1 << to) 。同时，dp值也要加上 from 到 to 的这条边的边权，即 dp[state ~|~ (1 << to)] = \min\{dp[state][from] + dis[from][to])\}

#include <bits/stdc++.h>
#define N 21
using namespace std;
int a[N][N], dp[1 << N][N], n, ans = 2e9;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n;
    for(int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> a[i][j];
    memset(dp, 0x3f, sizeof(dp));
    dp[1][0] = 0;
    for(int s = 1; s < (1 << n); s++) for(int i = 0; i < n; i++) {
        if ((s >> i) & 1) for(int j = 0; j < n; j++) {
            if ((s >> j) & 1) continue;
            dp[s | (1 << j)][j] = min(dp[s | (1 << j)][j], dp[s][i]+a[i][j]);
        }
    }
    cout << dp[(1 << n)-1][n-1];
    return 0;
}

新问题

从一个点出发，经过所有 n 个点后回到起点 （可重复经过） ，求最短线路。

• n \le 15

还是 dp[state][i] 表示经过了 state 中的点，最后一个点为 i 的最短线路。不过由于可以重复走，dp 前应先做一遍 Floyd 。

转移

同上。