欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-23 21:45:10
...

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;
}
相关标签: 状压dp