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[15][15];
int dp[1<<12][15];
int main()
{
    int n;
    scanf("%d",&n);
    while(n)
    {
        for(int i=0;i<=n;i++)
        {
            for(int j=0;j<=n;j++)
            {
                scanf("%d",&pho[i][j]);
            }
        }
        for(int k=0;k<=n;k++)
        {
            for(int i=0;i<=n;i++)
            {
                for(int j=0;j<=n;j++)
                {
                    pho[i][j]=min(pho[i][k]+pho[k][j],pho[i][j]);
                }
            }
        }
        for(int s=0;s<=(1<<n)-1;s++)
        {
            for(int i=1;i<=n;i++)
            {
                if(s&(1<<(i-1)))
                {
                    if(s==(1<<(i-1)))
                    {
                        dp[s][i]=pho[0][i];
                    }
                    else
                    {
                        dp[s][i]=inf;
                        for(int j=1;j<=n;j++)
                        {
                            if((s&(1<<(j-1)))&&i!=j)
                            {
                                dp[s][i]=min(dp[s][i],dp[s^(1<<(i-1))][j]+pho[j][i]);
                            }
                        }
                    }
                }
            }
        }
        int ans=inf;
        for(int i=1;i<=n;i++)
        {
            ans=min(ans,dp[(1<<n)-1][i]+pho[i][0]);
        }
        printf("%d\n",ans);
        scanf("%d",&n);
    }
}

POJ 3311 【状态压缩DP】

推荐阅读