P1171 售货员的难题

问题

P1171 售货员的难题
给定一个图，问从 $1$ 点出发，经过所有点恰好一次，返回 $1$ 点的最短距离。
数据规模：$n \le 20$。

这是一个典型的 NP 问题，TSP 旅行商问题，目前已知最优的解法就是状压DP。

由于我们需要从起点经过每个点一次，最后回到原点，所以可以记 mask 表示当前走过了哪些村庄。

接着考虑如何转移，那么显然我们发现还需要记录经过 mask 中的点之后，最后位于哪个点，于是我们就得到了定义：$f[mask][i]$ 表示从村庄 $1$ 出发，访问了 mask 中的点之后，最后停留在 $i$ 的最短距离。

初始化 f[0][1] = 0，接着考虑转移：$f[mask \cup j][j] = \min(f[mask \cup j][j], f[mask][i] + w[i][j])$。最后我们考虑从满状态走回到初始村庄的代价，即可。

为什么要特殊把 1 号村庄拿出来？因为如果直接放在内部 DP 的话，无法保证最后才走回到 1，而且不好处理这种回路的问题。

不过这里我还有想到一种思路，为什么不写两个 DP，正向 f 与反向 g，然后再考虑从中间点拼接呢？但这样仍然逃不过子集枚举，反而让状态之间的合并更复杂了。

这题是典型的：已完成集合状态 + 当前所在位置。

代码

▶

P1171

const int maxn = 20 + 5;
const int maxS = (1 << 20) + 5;

ll mat[maxn][maxn];
ll dis[maxS][maxn];

void solve( ) {
    int n = read( );
    for( int i = 1; i <= n; ++ i ) {
        for( int j = 1; j <= n; ++ j ) {
            mat[i][j] = read( );
        }
    }

    int N = (1 << n) - 1;
    for( int i = 0; i <= N; ++ i ) {
        for( int j = 1; j <= n; ++ j ) {
            dis[i][j] = inf;
        }
    }

    dis[1][1] = 0;
    for( int mask = 0; mask <= N; ++ mask ) {
        for( int i = 1; i <= n; ++ i ) {
            if( dis[mask][i] == inf ) continue;
            for( int j = 2; j <= n; ++ j ) {
                int pos = ( 1 << ( j - 1 ) );
                if( mask & pos ) continue;
                int nxt = mask | pos;
                dis[nxt][j] = min( dis[nxt][j], dis[mask][i] + mat[i][j] );
            }
        }
    }

    ll ans = inf;
    for( int j = 2; j <= n; ++ j ) {
        ans = min( ans, dis[N][j] + mat[j][1] );
    }
    cout << ans << '\n';
}