[算法竞赛进阶指南]Hamilton路径(状压dp)

╰+哭是因爲堅強的太久メ 2022-02-20 10:22 241阅读 0赞

# [F : \[算法竞赛进阶指南\]Hamilton路径][F _ _Hamilton] #

状压dp  
dp\[i\]\[j\]表示在i点处，状态为j下，起点到该点的最短路径  
状态0表示不经过，1表示经过  
比如dp\[3\]\[13\],状态13在二进制下是1101，也就是从0到3经过点2，没有过1  
在dp过程中，到达该点是从哪个点过来路径最短的，i^1<<j把第j个点的状态取反，即到达第j个点是从状态0101来的

#include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    const int INF=0x3f3f3f3f;
    int n;
    int weight[25][25]; //保存权值
    int dp[25][1<<20]; //dp[i][j]表示在i点处，状态为j下，起点到该点最短路径为dp[i][j]
    int findMin(int n)
    { 
        memset(dp,INF,sizeof(dp));
        dp[0][1]=0; //起点赋初值，只经过了0路径为0
        for(int i=1;i<1<<n;i++) //枚举所有状态,在所有状态下，起点到各点的最短路径
        { 
            for(int j=0;j<n;j++)
            { 
                if(i&(1<<j)) //取出状态i中第j个点的状态，如果是1表示经过
                { 
                    for(int k=0;k<n;k++) //判断在经过j点前还经过哪些点
                    { 
                        // i^1<<j把i在二进制下的第j位取反，因为此前还没有到达过j点
                        if((i^1<<j)>>k&1) //在经过j点前，是否经过第k个点,比如1101，在到达第2个点时，是否经过了第0，1，3点，这个状态表示不经过1点
                        { 
                            dp[j][i]=min(dp[j][i],dp[k][i^1<<j]+weight[j][k]);
                        }
                    }
                }
            }
        }
        return dp[n-1][(1<<n)-1];
    }
    int main()
    { 
        //freopen("test.txt","r",stdin);
        cin>>n;
        for(int i=0;i<n;i++)
        { 
            for(int j=0;j<n;j++)
            { 
                cin>>weight[i][j];
            }
        }
        cout<<findMin(n)<<endl;
        return 0;
    }

[F _ _Hamilton]: http://acm.ncst.edu.cn/contest_problem.php?cid=1025&pid=5