「算法竞赛进阶指南」0x01 最短Hamilton路径 解题报告

题目在这里啊题目在这里~

Hamilton路径：将所有点都遍历刚好一次的路径

思路：

数据范围比较小（1~20），所以我们可以考虑暴力中的枚举

数组f[i][j] i的二进制表示选取了哪些点 j表示以哪个点结尾

然后就是状态压缩

由于求的是最小值，所以一开始的时候要赋初值INF

为了有解，f[1][0]应该赋值为0.

#include<bits/stdc++.h>
#define INF 0x7f7f7f7f
#define Max (1<<n)
using namespace std;
int n;
int a[20][20];
int f[1<<20][20];
int res;
int read()
{
    int s=0;
    char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
    {
        s=(s<<1)+(s<<3)+c-'0';
        c=getchar();
    }
    return s;
}
void Hamilton()
{
    int i,j,k;
    f[1][0]=0;
    for(i=2;i<Max;i++)
    {
        for(j=0;j<n;j++)
        {
            f[i][j]=INF;
            if((i>>j)&1)
            {
                res=i^(1<<j);
                for(k=0;k<n;k++)
                    if((res>>k)&1)
                        f[i][j]=min(f[i][j],f[res][k]+a[k][j]);
            }
        }
    }
    return;
}
int main()
{
    int i,j;
    n=read();
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            a[i][j]=read();
    Hamilton();
    printf("%d\n",f[Max-1][n-1]);
    return 0;
}