首页 > 代码库 > hdu 3001(状压dp+三进制)
hdu 3001(状压dp+三进制)
不管是几进制,都用的是逻辑上概念,(上次六进制是用来转化多维数据)核心思路是TSP。这里的预处理比较巧妙,计算出了每种状态下各个位上的模vis[][]。
TSP:dp[i][j] 在i状态下,以j结尾的最优解。两种转移都行:我为人人,人人为我。
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #define maxn 60000 #define inf 0x3f3f3f3f const double eps=1e-8; using namespace std; int dp[maxn][12]; int maps[13][12]; int vis[maxn][12]; int state[12]; int n,m; void init() { state[0]=1; for(int i=1;i<11;i++) state[i]=state[i-1]*3; for(int i=0;i<=state[10];i++) { int x=i; for(int j=0;j<10;j++) vis[i][j]=x%3,x/=3; } } int main() { // freopen("in.txt","r",stdin); while(~scanf("%d%d",&n,&m) ) { init(); memset(maps,0x3f,sizeof(maps)); for(int i=0;i<m;i++) { int u,v,k; scanf("%d%d%d",&u,&v,&k); maps[u-1][v-1]=maps[v-1][u-1]=min(maps[u-1][v-1],k); } int tag,ans=inf; memset(dp,0x3f,sizeof(dp)); for(int i=0;i<n;i++) dp[state[i]][i]=0; for(int i=0;i<state[n];i++) { tag=1; for(int j=0;j<n;j++) { if(vis[i][j]==0) tag=0;//这个判断特别巧妙,因为j会循环,里面存放了i的情况 if(dp[i][j]==inf) continue; for(int k=0;k<n;k++) { if( k!=j && vis[i][k]<2 && maps[k][j]!=inf) dp[i+state[k] ][k]=min( dp[i+state[k] ][k],dp[ i ][j]+maps[j][k] );//上次写的那个是前向后,这个是后向前,比较好写。人人为我,我为人人 } } if(tag) for(int j=0;j<n;j++) ans=min(ans,dp[i][j]); } if (ans == inf) ans = -1; cout<<ans<<endl; } return 0; }
hdu 3001(状压dp+三进制)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。