题解 P1433 【吃奶酪】

· · 题解

upd：修改了关于NP-hard的一个原则性错误

这里提供另外一种状压dp，同时此题作为TSP（几乎）的模板题，顺便详细地解释一下旅行商问题（TSP）。

TSP

原题：

有n个城市，从起点 0 开始游历每一个城市，只访问每个城市一次，最后回到起点，所需要的最短路径是多少？

OI界尚未发现本题多项式时间复杂度的解法。我们可以穷举全排列，从而获得一个\Theta((n-1)!)的做法。

然而这通常会TLE，所以需要优化。模拟退火是一个很好的思路，但是正确率有时不能得到保证，参见其他题解，此处不再赘述。

我们可以对集合来dp。令f[S][i]表示从i出发，还剩下点集S未走。那么不难发现可以逆推：

\begin{cases}f[\emptyset][i]=0,0\le i\le n\\f[S][i]=f[S+\{j\}][j]+dist(i,j),0\le i,j\le n\\Ans=f[\emptyset][0]\end{cases}

那么点集如何表示呢？此类问题由于是NP-hard问题（如果不清楚此类概念可以在luogu日报中寻找），n一般很小，所以可以状态压缩，设S_i表示S的二进制第i位，S_i=0\ or\ 1表示是否i在集合内。

那么只需要一些简单位运算即可（参见代码），同时记得floyd预处理dist。

不难发现本题就是TSP问题，因为最短路径一定是直线距离，所以无需floyd。

#include<bits/stdc++.h>
using namespace std;
#define reg register
double dp[1<<16][17],dist[17][17],x[17],y[17];
int n;
inline void init(){
    scanf("%d",&n);
    for(reg int i=1;i<=n;++i)
        scanf("%lf%lf",x+i,y+i);
    x[0]=y[0]=0;
    for(reg int i=0;i<=n;++i)
        for(reg int j=0;j<=n;++j)
            dist[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
    memset(dp,127,sizeof dp);
}
inline void solve(){
    for(reg int i=0;i<=n;++i)dp[(1<<n+1)-1][i]=0;
    for(reg int S=(1<<n+1)-2;~S;--S)
        for(reg int i=0;i<=n;++i)
            for(reg int j=0;j<=n;++j)
                if(!(S&1<<j))dp[S][i]=min(dp[S][i],dp[S|1<<j][j]+dist[i][j]);
    printf("%.2lf",dp[0][0]);
}
int main(){
    init();
    solve();
    return 0;
}