hdu 3001 Travelling (状态压缩dp-----模拟三进制）

每个点最多走两次的tsp

用三进制记录每个点到的次数。

dp方程：dp[i][j]=min(dp[i][j],dp[i-bit[j]][k]+mp[k][j])  【i中bit[j]不为0---i状态中j点去过 且mp[k][j]!=0】

（上面为2进制表示的最短路径dp的变形：dp[i][j]=min(dp[i][j],dp[i&(~(1<<j))][k]+mp[k][j])  

【i&(1<<k)=1 且mp[k][j]!=0】dp[i][j]表示i状态目前在j点。

i&(~（1<<j))其实就是i状态中去掉j位的1 。把j位取反变0和i作与运算。）

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define INF 0xffffff

using namespace std;

int bit[12]={0,1,3,9,27,81,243,729,2187,6561,19683,59049};
int dp[59100][11];    //dp[i][j]表示i状态此刻在j点
int mp[11][11],t[59100][11];
//t[i][j]记录i状态时j位上的数（0或1或2）
//表示i状态时j点去过几次 0---没去过，1---去过1次，2---去过两次

void init()   //模拟三进制,预处理
{
    for(int i=0;i<59050;i++)
    {
        int x=i;
        for(int j=1;j<=10;j++)
        {
            t[i][j]=x%3;
            x/=3;
            if(x==0) break;
        }
    }
}

int main()
{
    int m,n,a,b,c,flag;
    init();
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(mp,0x3f,sizeof(mp));
        memset(dp,0x3f,sizeof(dp));

        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            if(c<mp[a][b]) mp[a][b]=mp[b][a]=c;//判断重边
        }
        for(int i=0;i<=n;i++)
            dp[bit[i]][i]=0;
        int ans=INF;
        for(int i=0;i<bit[n+1];i++)
        {
            flag=1;
            for(int j=1;j<=n;j++) //选终点
            {
                if(!t[i][j])
                {
                    flag=0;
                    continue;
                }
                for(int k=1;k<=n;k++) //选以j为终点的路径上的中转点，更新最短路径
                {
                    if(t[i][k]==0) continue;
                    int l=i-bit[j];
                    dp[i][j]=min(dp[i][j],dp[l][k]+mp[k][j]);
                }
            }
            if(flag)  //每一位都为1了，n个地方都走到了，更新ans
            {
                for(int j=1;j<=n;j++)
                    ans=min(dp[i][j],ans);
            }
        }
        if(ans==INF) puts("-1");
        else printf("%d\n",ans);
    }
    return 0;
}

hdu 3001 Travelling (状态压缩dp-----模拟三进制）

原文：http://blog.csdn.net/u012841845/article/details/19006443