P1171 售货员的难题暴力dp

著名的TSP问题，NPC问题

对于数据大的情况，我们可以使用一系列近似算法进行寻找解。

对于数据规模小的情况，我们可以直接暴力dp

一开始写了一个dfs，然后就被n=20的数据卡爆了

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

using std::min;

const int maxn=22;

int f[1<<maxn][maxn];

int M[maxn][maxn];

int n;

int dfs(int base,int now)

{

    if(base&1==0)   return f[base][now]=0x7fffffff;

    if(f[base][now])    return f[base][now];

    int ans=0x7ffffff;

    for(int i=0;i<n;i++)

        if(base&(1<<i)&&i+1!=now)

            ans=min(ans,dfs(base^(1<<(now-1)),i+1)+M[i+1][now]);

    return f[base][now]=ans;

}

int main()

{

    scanf("%d",&n);

    f[1][1]=1;

    for(int i=1;i<=n;i++)

        for(int j=1;j<=n;j++)

        {

            scanf("%d",&M[i][j]);

            if(i==j)    M[i][j]=0x7ffffff;

        }

    for(int i=1;i<=n;i++)

    {

        M[i][n+1]=M[i][1];

        M[n+1][i]=M[1][i];

    }

    n++;

    dfs((1<<n)-1,n);

    printf("%d",f[(1<<n)-1][n]-1);

}

然后就回去补了一发递推，还是递推常数小呀。

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<cstring>

using std::min;

const int maxn=20,inf=0x7ffffff;

int f[1<<maxn][maxn];

int M[maxn][maxn];

int n;

int main()

{

    memset(f,127,sizeof(f));

    scanf("%d",&n);

    for(int i=0;i<n;i++)

        for(int j=0;j<n;j++)

            scanf("%d",&M[i][j]);

    for(int i=0;i<n;i++)   M[i][i]=inf;

    f[1][0]=0;

    for(int i=1;i<(1<<n);i++)

        for(int j=0;j<n;j++)

            if(i&(1<<j))

                for(int k=0;k<n;k++)

                    if((i&(1<<k))==0)

                        f[i^(1<<k)][k]=min(f[i^(1<<k)][k],f[i][j]+M[j][k]);

    int ans=inf;

    for(int i=1;i<n;i++)

        ans=min(ans,f[(1<<n)-1][i]+M[i][0]);

    printf("%d",ans);

}

感觉dp在noip会是我的大难♂题

巴特西

P1171 售货员的难题暴力dp

最新文章

热门文章

巴特西

P1171 售货员的难题 暴力dp

最新文章

热门文章

P1171 售货员的难题暴力dp