自动搬运

查看原文

来自洛谷，原作者为

	niiick **

搬运于2025-08-24 21:22:03，当前版本为作者最后更新于2018-02-21 13:45:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

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

$dp[i][j]$表示 从起点到第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]);$

$i|(1<<j-1)$ 将状态$i$的第$j$为置为1得到下一步的状态

$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;
}