#include<bits/stdc++.h> using namespace std; int main() { int n,k; scanf("%d%d",&n,&k); int ans1=n&((1<<k)-1);//提取n在二进制状态下第0到k-1位所对应的十进制数 int ans2=(n>>k)&1; int ans3=n xor (1<<k);//n在二进制状态下第k位取反 int ans4=n | (1<<k);//n在二进制状态下第k位赋值1 int ans5=n&(~(1<<k));//n在二进制状态下第k位赋值为0 printf("%d %d %d %d %d",ans1,ans2,ans3,ans4,ans5); return 0; }
先说暴力做法:枚举n个点的全排列,计算路径长度取最小值,显然,时间复杂度炸了
如何优化?
使用一个n位的二进制数,若其第i位为1,则表示第i个点已被经过。任意时刻需知道当前所处的位置,F[i,j]
i对应的二进制数表示“点被经过的状态”,目前处于j时的最短路径
起点设置F[1,0]=0,只经过了点0(i只有第0位为1),目前处于起点0,最短路长度0。
为了方便,F数组其他数值设为无穷大。
最终目标为F[(1<<n)-1,n-1],即经过所有点,处于终点n-1的最短路
#include<bits/stdc++.h> using namespace std; int n; int weight[20][20]; int f[1<<20][20]; int hamilton(int n); int main() { scanf("%d",&n); for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { cin>>weight[i][j]; } } hamilton(n); cout<<f[(1<<n)-1][n-1]<<endl; return 0; } int hamilton(int n) { memset(f,0x3f,sizeof(f)); f[1][0]=0; for(int i=1;i<=(1<<n)-1;i++) { for(int j=0;j<n;j++) if(i>>j&1) { for(int k=0;k<n;k++) { if(i>>k&1) { f[i][j]=min(f[i][j],f[i^1<<j][k]+weight[k][j]); } } } } return f[(1<<n)-1][n-1]; }
ps:大小关系比较的运算符优先于“位与”“异或”“位或”运算
写运算程序时尽量加括号