题解 P1171 【售货员的难题】

· · 题解

TSP问题，也算是状压DP经典吧

我们以一串二进制数表示村庄的集合（状态）

1表示该村庄访问过，0表示没有

**从起点到第j号点** 且到达时**状态恰好为i的最短路** 则最后答案就是$min(dp[(1<< n) -1][i] + map[i][1])$ $(2<=i<=n)

其中map数组是题目给定的各村庄间距离

而求取dp数组的方法 我们可以借鉴Floyd的思想

具体代码：

for(int i=0;i<=(1<<n)-1;++i)
for(int j=1;j<=n;++j)
if( ( (1<<j-1)&i )==0 )
for(int k=1;k<=n;++k)
if( ( (1<<k-1)&i) )
dp[i|(1<<j-1)][j]=min(dp[i|(1<<j-1)][j],dp[i][k] + rem[k][j]);

如何解释呢

第一层循环 i 枚举每个状态

第二层循环 j 枚举下一步到达的点

if( !( (1 << j-1) & i) ) 这句判断 j 是否已访问

1左移j-1位，则此时只有第j位是1

若状态 i 的第 j 位为1，则&与运算返回1，表示已访问，否则没访问

第三层循环枚举中介点k， 其中if语句判断同上

dp[i|(1<<j-1)][j]=min(dp[i|(1<<j-1)][j],dp[i][k] + rem[k][j]); $dp[i][k] + map[k][j]$表示在当前状态i中寻找中介点检查最短路是否可以更新 ``` //niiick #include<iostream> #include<cstdio> #include<vector> #include<algorithm> #include<queue> #include<cstring> using namespace std; int read() { int f=1,x=0; char ss=getchar(); while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();} while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();} return f*x; } const int maxn=1100010; int n,ans=2e9; int dp[maxn][25]; int rem[25][25]; int main() { n=read(); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) rem[i][j]=read(); memset(dp,67,sizeof(dp)); dp[1][1]=0;//状态1表示此时只有1号点访问过 for(int i=0;i<=(1<<n)-1;++i)//dp过程解释如上 for(int j=1;j<=n;++j) if( ( (1<<j-1)&i )==0 ) for(int k=1;k<=n;++k) if( ( (1<<k-1)&i) ) dp[i|(1<<j-1)][j]=min(dp[i|(1<<j-1)][j],dp[i][k] + rem[k][j]); for(int i=2;i<=n;i++)//最后从状态(1<<n)-1（二进制全为1）中寻找到1最短的点 ans=min(ans,dp[(1<<n)-1][i] + rem[i][1]); printf("%lld",ans); return 0; } ``` n<=20的数据范围在状压题中算是开到极限了，蒟蒻担心卡常所以开了O2，最大的点跑了541ms，目测不开O2也是能过的 ********************** #### 9.15——Update 再提供一种**状压搜索**的思路，~~虽然试了好几次都卡不过最后一个点~~，所以仅供参考学习吧，因为这种思路也挺常用的 dp数组含义依然同上， 初始$dp[1][1]=0

搜索具体代码，应该不难理解

void dfs(int x,int u)//x是当前状态，u是当前到达的结点
{
    for(int i=1;i<=n;++i)
    if(((1<<i-1)&x)==0)//枚举还未到达的点
    if(dp[x|(1<<i-1)][i]>dp[x][u]+rem[u][i])//如果可以更新就继续搜索
    {
        dp[x|(1<<i-1)][i]=dp[x][u]+rem[u][i];
        dfs(x|(1<<i-1),i);
    }
}

最终答案判断方法与上述DP相同

虽然这种方法艹不过此题,但建议要理解这种思路

#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
typedef double dd;

int read()
{
    int f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}

const int maxn=1050000;
int n,ans=2e9;
int rem[22][22],dp[maxn][22];

void dfs(int x,int u)
{
    for(int i=1;i<=n;++i)
    if(((1<<i-1)&x)==0)
    if(dp[x|(1<<i-1)][i]>dp[x][u]+rem[u][i])
    {
        dp[x|(1<<i-1)][i]=dp[x][u]+rem[u][i];
        dfs(x|(1<<i-1),i);
    }
}

int main()
{
    n=read();
    for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
    rem[i][j]=read();

    memset(dp,67,sizeof(dp)); dp[1][1]=0;
    dfs(1,1);

    for(int i=1;i<=n;++i) 
    ans=min(ans,dp[(1<<n)-1][i]+rem[i][1]);
    printf("%d",ans);
    return 0;
}