HDU 3001 Travelling (状态压缩DP)

题意：有n个点（n<=10），m条边的图（可能有重边），问从任一点走遍整个图的最短费用和，其中每个点最多只能经过两次。

思路：tsp问题，状压dp。三进制压缩一个点已被访问的次数作为状态s，dp[s][i]代表状态s下最后一个到达的点位i的最小费用。递推方程：在dp[s][i]已计算出来的情况下，枚举下一个到达的点k，那么dp[news][k] = min{ dp[news][k]+Edge[i][k],dp[news][k] },初始化：dp为INF，dp[3的i次方][i]=0.

注意题目存在重边，因此只保留边长最小的。

两种写法，递推的效率高但顺序相对难掌握，记忆化搜索好些但效率下。

递推：

#include
  
   
#include
   
     #include
    
      #define INF 0x3f3f3f3f using namespace std; int n,m; int tri[12],dig[59050][12];//dig[s][i]表示状态s的第i位 int dp[59050][12]; int Edge[11][11]; int ans; void init()//初始化计算tri[i]为3的i次方和dig[s][i] { tri[0]=1; for(int i=1;i<=10;++i) tri[i] = tri[i - 1] * 3; for(int s=0;s<59049;++s) for(int i=0,t = s;i<10;++i,t/=3) dig[s][i]=t%3; } void input() { int a,b,c; memset(Edge,INF,sizeof(Edge)); while(m--) { scanf("%d%d%d",&a,&b,&c); --a,--b; Edge[b][a]=Edge[a][b]=min(Edge[a][b],c);//存在重边，只记录边长最小的 } } void getdp() { memset(dp,INF,sizeof(dp)); ans = INF; for(int i=0;i
     
      =2) continue;//如果不存在边
      
       或者k已被访问2次以上则不进行更新 int news = s + tri[k];//news表示在s的基础上再访问k一次所得状态 dp[news][k] = min(dp[news][k],dp[s][i]+Edge[i][k]); } } if(vall) for(int i=0;i
       
        >n>>m) { input(); getdp(); getans(); } return 0; } 
       
      
     
    
   
  

记忆化搜索：

#include
  
   
#include
   
     #include
    
      #define INF 0x3f3f3f3f using namespace std; int n,m; int tri[12],dig[59050][12]; int dp[59050][12]; int Edge[11][11]; int ans; void init() { tri[0]=1; for(int i=1;i<=10;++i) tri[i] = tri[i - 1] * 3; for(int s=0;s<59049;++s) for(int i=0,t = s;i<10;++i,t/=3) dig[s][i]=t%3; } void input() { int a,b,c; memset(Edge,INF,sizeof(Edge)); while(m--) { scanf("%d%d%d",&a,&b,&c); --a,--b; Edge[b][a]=Edge[a][b]=min(Edge[a][b],c); } } int dfs(int s,int i) { if(dp[s][i]!=-1) return dp[s][i]; //体现记忆化 int cur = INF;//初始化为INF，如果出现不合法状态会返回INF if(s==tri[i]) cur = 0;//如果s中，仅有i被访问且只被访问一次 else if(dig[s][i])//如果i在s中确实被访问了 for(int k=0;k
     
       cur = min(cur,dfs(s-tri[i],k)+Edge[k][i]); return dp[s][i] = cur; } void getdp() { memset(dp,-1,sizeof(dp)); ans = INF; for(int s=0;s
      
       >n>>m) { input(); getdp(); getans(); } return 0; }