[poj3311]Hie with the Pie(Floyd+状态压缩DP)

题意：tsp问题，经过图中所有的点并回到原点的最短距离。

解题关键：floyd+状态压缩dp，注意floyd时k必须在最外层

转移方程：$dp[S][i] = \min (dp[S \wedge (1 < < (i - 1))][k] + dis[k][j],dp[S][i])$

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<cmath>

#define inf 100000000

using namespace std;

int dis[][];

int dp[<<][];

int n,ans;

int main(){

    while(scanf("%d",&n)&&n){

        for(int i=;i<=n;i++)for(int j=;j<=n;j++)scanf("%d",&dis[i][j]);

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

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

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

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

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

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

                if(S&(<<(i-)))//状态S中已经过城市i

                {

                    if(S==(<<(i-)))    dp[S][i]=dis[][i];

                    else{

                        dp[S][i]=inf;

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

                            if(S&(<<(j-))&&i!=j)//枚举不是城市I的其他城市

                                dp[S][i]=min(dp[S^(<<(i-))][j]+dis[j][i],dp[S][i]);

                        }

                    }

                }

            }

        int ans=inf;

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

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

        }

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

    }

    return ;

}

改进了一下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<cmath>

#define inf 100000000

using namespace std;

int dis[][];

int dp[<<][];

int n,ans;

int main(){

    while(scanf("%d",&n)&&n){

        for(int i=;i<=n;i++)for(int j=;j<=n;j++)scanf("%d",&dis[i][j]);

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

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

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

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

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

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

                if(S&(<<i))//状态S中已经过城市i

                {

                    if(S==(<<i))    dp[S][i]=dis[][i];

                    else{

                        dp[S][i]=inf;

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

                            if(S&(<<j)&&i!=j)//枚举不是城市I的其他城市

                                dp[S][i]=min(dp[S^(<<i)][j]+dis[j][i],dp[S][i]);

                        }

                    }

                }

        printf("%d\n",dp[(<<(n+))-][]);

    }

    return ;

}

巴特西

[poj3311]Hie with the Pie(Floyd+状态压缩DP)

最新文章

热门文章