POJ 3311 Hie with the Pie （Floyd+状态压缩）

题目链接~~>

做题感悟：本来做背包题的，其中牵扯到TSP问题结果就晕了，于是就学TSP但是这题貌似不是正宗的TSP问题。

解题思路：Floyd + 状态压缩

                 第一步：先用Floyd 处理一下图得到任意两点之间的最短路。

                 第二步：状态压缩枚举所有情况，dp [ i ] [ j ] 代表在状态 i 下（i 表示成二进制，某位为 0 代表未经过此点，如果为 1 代表经过此点）从 0 点出发到经过状态 i 中的所有点后到达 j 的最短路径。

                       动态方程：dp [ i ] [ j ]  = min { dp [ i ^(1<< i ) ] [ j ] + d[ j ] [ i ] ,dp [ i ] [ j ] },其中 j 存在于状态 i 中，其实和Floyd 的原理差不多，表示以 j 为中间点后是否使路径更短。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iomanip>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #define INT long long int
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const int INF = 99999999 ;
     
    
   

    

     

    
    

     

      const int MX = 10 + 10 ;
     
    
   

    

     

    
    

     

      int n ;
     
    
   

    

     

    
    

     

      int dp[1<<11][MX],d[MX][MX] ;
     
    
   

    

     

    
    

     

      void Floyd() // 求任意两点之间的最短路径
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     

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

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void DP_SC()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 for(int S=0 ;S<(1<<n) ;S++) // 枚举所有状态
     
    
   

    

     

    
    

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

    

     

    
    

     
 if(S&(1<<(i-1)))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(S==1<<(i-1))  dp[S][i]=d[0][i] ; // 如果就一个点 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]+d[j][i]) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 int S = (1<<n)-1 ;
     
    
   

    

     

    
    

     
 int ans = dp[S][1]+d[1][0] ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       ans = min(dp[S][i]+d[i][0],ans) ;
     
    
   

    

     

    
    

     
 cout<<ans<<endl ;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     

       Floyd() ;
     
    
   

    

     

    
    

     

       DP_SC() ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iomanip>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #define INT long long int
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const int INF = 999999999 ;
     
    
   

    

     

    
    

     

      const int MX = 10 + 10 ;
     
    
   

    

     

    
    

     

      const int MY = 11 ;
     
    
   

    

     

    
    

     

      int n ;
     
    
   

    

     

    
    

     

      int dp[1<<MY][MX],d[MX][MX] ;
     
    
   

    

     

    
    

     

      void Floyd() // 求最短路
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     

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

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void DP_SC()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 memset(dp,-1,sizeof(dp)) ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       dp[1<<i][i]=d[0][i] ;
     
    
   

    

     

    
    

     
 for(int S=0 ;S<(1<<n) ;S++) // 枚举每一种状态
     
    
   

    

     

    
    

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

    

     

    
    

     
 if(dp[S][i]!=-1) // 以 i 点为中间点更新 j 点
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

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

    

     

    
    

     
 if(i!=j&&!(S&(1<<j)))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(dp[S|(1<<j)][j]==-1)
     
    
   

    

     

    
    

     

       dp[S|(1<<j)][j]=dp[S][i]+d[i][j] ;
     
    
   

    

     

    
    

     
 else dp[S|(1<<j)][j]=min(dp[S][i]+d[i][j],dp[S|(1<<j)][j]) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 int ans = INF ; // 寻找最优解
     
    
   

    

     

    
    

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

    

     

    
    

     
 if(dp[(1<<n)-1][i]!=-1)
     
    
   

    

     

    
    

     

       ans = min(ans,dp[(1<<n)-1][i]+d[i][0]) ;
     
    
   

    

     

    
    

     
 cout<<ans<<endl ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       n++ ;
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     

       Floyd() ;
     
    
   

    

     

    
    

     

       DP_SC() ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/37935303