HDU 3001 三进制状压DP

题意

N个城市，M条路。类似于TSP问题的一个问题，与TSP不同的是每个城市最多可以访问两次。

题解

由于每个城市可访问两次，因此这里需要用到三进制状压。三进制状压与二进制状压还是有一定差别的。三进制状压需要自行初始化十进制转三进制表。然后剩下的就与二进制状压差不多了。对一些不符合条件的状态进行过滤，需要特别注意，尽管每个城市可以访问两次，但只要每个城市至少访问一次就算完成任务。因此，针对每个状态，都需要判断一下是否访问了所有城市，如果访问了所有城市，那么这个状态就参与最终结果的计算。

注意事项

有个细节需要特别注意。dig[i][k]>=2，不能进行状态转移。因为这种情况代表状态i中访问K点的次数已经超过2，如果强行状态转移会造成访问K点次数超过限制的问题。

代码

#include <iostream> #include<cstdio> #include<algorithm> #include<cstring> #define INF 0x1f1f1f1f using namespace std; int num[]={0,1,3,9,27,81,243,729,2187,6561,19683,59049}; int dig[59060][12]; int edge[12][12]; int dp[59060][12]; int main() { int n,m; for(int i=0;i<59050;i++){ int x=i; int pos=1; while(x>0){ dig[i][pos++]=x%3; x/=3; } } while(~scanf("%d%d",&n,&m)){ memset(edge,INF,sizeof(edge)); memset(dp,INF,sizeof(dp)); for(int i=0;i<m;i++){ int a,b,w; scanf("%d%d%d",&a,&b,&w); if(w<edge[a][b]) edge[a][b]=edge[b][a]=w; } for(int i=1;i<=n;i++){ dp[num[i]][i]=0; } int ans=INF; for(int i=0;i<=num[n+1]-1;i++){ bool all=true; for(int j=1;j<=n;j++){ if(dig[i][j]==0){ all=false; } if(dp[i][j]==INF) continue; for(int k=1;k<=n;k++){ if(j==k) continue; if(edge[j][k]==INF||dig[i][k]>=2) continue; dp[i+num[k]][k]=min(dp[i+num[k]][k],dp[i][j]+edge[j][k]); } } if(all){ for(int j=1;j<=n;j++){ ans=min(ans,dp[i][j]); } } } if(ans==INF){ puts("-1"); }else{ printf("%d\n",ans); } } return 0; }