POJ 3311 【状态压缩DP】

题意：

给n个点，给出矩阵代表i到j单向边的距离。

要求，不介意访问每个点的次数，要求访问完每个点，使得路程总和最小。

思路：

由于不介意访问每个点的次数，所以可以先进行FLOYD求出任意两个点之间的最短路，然后就是DP。

同样的，1代表有访问过，0代表没访问过。

dp[s][j]代表访问状态为s的情况下最终到达点j的最优值。

枚举状态s中每一个可以到达的点，从所有可能的点中枚举对其进行更新。

关于状态压缩的细节方面，注意从左边数第i位是从0开始数的，所以第i位代表第i+1个点。

然后状态的总数2^(n)-1.

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

//dp[s][i]代表从s状态到达城市i的最佳策略

const int inf=0x3f3f3f3f;

int pho[][];

int dp[<<][];

int main()

{

    int n;

    scanf("%d",&n);

    while(n)

    {

        for(int i=;i<=n;i++)

        {

            for(int j=;j<=n;j++)

            {

                scanf("%d",&pho[i][j]);

            }

        }

        for(int k=;k<=n;k++)

        {

            for(int i=;i<=n;i++)

            {

                for(int j=;j<=n;j++)

                {

                    pho[i][j]=min(pho[i][k]+pho[k][j],pho[i][j]);

                }

            }

        }

        for(int s=;s<=(<<n)-;s++)

        {

            for(int i=;i<=n;i++)

            {

                if(s&(<<(i-)))

                {

                    if(s==(<<(i-)))

                    {

                        dp[s][i]=pho[][i];

                    }

                    else

                    {

                        dp[s][i]=inf;

                        for(int j=;j<=n;j++)

                        {

                            if((s&(<<(j-)))&&i!=j)

                            {

                                dp[s][i]=min(dp[s][i],dp[s^(<<(i-))][j]+pho[j][i]);

                            }

                        }

                    }

                }

            }

        }

        int ans=inf;

        for(int i=;i<=n;i++)

        {

            ans=min(ans,dp[(<<n)-][i]+pho[i][]);

        }

        printf("%d\n",ans);

        scanf("%d",&n);

    }

}

巴特西

POJ 3311 【状态压缩DP】

最新文章

热门文章