题目描述
求一条哈密顿回路
即所有的点经过且仅经过一次
用二进制数i表示已经过的点的情况
第j位为1表示已经经过
为0表示未经过
C++ 代码
#include<bits/stdc++.h>
#include<limits.h>
using namespace std;
int a[22][22],f[1<<20+1][21];
long long ans;
int n;
int main(){
cin>>n;
memset(f,0x7f7f7f7f,sizeof(f));
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>a[i][j];
f[1][0]=0;
for(int i=1;i<(1<<n);i++)
for(int j=0;j<=n-1;j++)
if((i>>j)&1==1)
for(int k=0;k<=n-1;k++)
if(((i^(1<<j))>>k)&1==1)
f[i][j]=min(f[i][j],f[i^(1<<j)][k]+a[k][j]);
cout<<f[(1<<n)-1][n-1];
}