步骤:
确定采用状压dp 范围20左右。
状态转移 f[i][j]表示对于第i个节点,它走到的第j个状态。对于任意状态,遍历任意节点,找到此节点并确定另一节点与其重合。
路径确定i>>j&1 路径重合i-(1<<j)>>k&1
遍历状态进行ans计算。
回路计数:https://www.lanqiao.cn/problems/1462/learning/?contest_id=73
大意是给出21个教学楼,如果编号互质,则两个教学楼间有一条路径。问有多少种情况可以走出哈密顿回路?
数据范围很小,很容易想到搜索,但是一定会爆时间。因此可以采用状压dp。
int m = 1<<nn; f[0][1] = 1; for(int i=0;i<m;i++){ for(int j=0;j<nn;j++){ if(i>>j&1){ for(int k=0;k<nn;k++){ if(i-(1<<j)>>k&1 && mapt[k][j]){ f[j][i]+=f[k][i-(1<<j)]; } } } } } ll ans = 0; for(int i=1;i<=nn;i++) ans+=f[i][m-1]; cout<<ans<<endl;
补给:https://www.luogu.com.cn/problem/P8733
大意是有n个村庄,需要走一遍且回到1号村庄。不能连续走d且不到一个村庄。问最少走多少距离。
很明确的也是哈密顿回路。因此我们可以继续使用之前的那个状态表示。因为这里的路径存在距离问题,因此需要用弗洛伊德预处理一下。
for(int k=0;k<n;k++){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++) mapt[i][j] = min(mapt[i][j],mapt[i][k]+mapt[k][j]); } } int m = 1<<nn; for(int i=0;i<n;i++){ for(int j=0;j<m;j++) f[i][j] = INF; } f[0][1] = 0; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if((i>>j)&1 == 1){ for(int k=0;k<n;k++){ if(((i-(1<<j))>>k)&1 == 1 ){ f[j][i] = min(f[j][i],f[k][i-(1<<j)]+mapt[k][j]); } } } } } double ans = 99999999; for(int i=1;i<n;i++){ ans = min(ans,f[i][m-1] + mapt[i][0]); } printf("%.2lf\n",ans);