POJ 2288 Islands and Bridges(状态压缩)

题目链接~~>

做题感悟：这题虽然看似很简单其实如果细心的话也不难，但是wa 了 n 次，wa 在了统计最优解个数上，开始没有开数组然后最后统计达到目标状态最优解的个数，这样是不对的，因为你只记录了最终的状态，可能在形成最优解的过程中有许多方法构成了最优解。

解题思路：

                (1) 、这题很容易想到状态方程 ： dp[ S ^ (1<<k) ] [ j ] [ k ] = max(dp[ S ^ (1<<k) ] [ j ] [ k ]  , dp[ S ] [ i ] [ j ]  +  Wk ) ;     dp[ S ^ (1<<k) ] [ j ] [ k ]  代表达到状态S ^ (1<<k) 并以 j , k 结尾的路径最优解 ；

                (2)、还要有记录路径的数组，因为有可能一种状态有许多方法构成 ，注意用 long long or __int64 ;

                (3)、注意只有一个点的情况。

代码：

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<ctime>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<stack>
     
    
   

    

     

    
    

     

      #include<cstring>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #define INT __int64
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const int INF = 9999999 ;
     
    
   

    

     

    
    

     

      const INT MY = 10 + 10 ;
     
    
   

    

     

    
    

     

      const INT MX = (1<<13) + 10 ;
     
    
   

    

     

    
    

     

      INT n ,m  ;
     
    
   

    

     

    
    

     

      INT dp[MX][MY][MY] ,v[MY] ,w[MY][MY] ,num[MX][MY][MY] ;
     
    
   

    

     

    
    

     

      void DP()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 for(INT S = 0 ;S < (1<<n) ;S++)
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     
 if(dp[S][i][j] != -1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(k == i || k == j || S & (1<<k) || !w[j][k]) continue ;
     
    
   

    

     

    
    

     

       INT mx = v[k] + v[j]*v[k] + dp[S][i][j] ;
     
    
   

    

     

    
    

     
 if(w[i][k])   mx += v[i]*v[j]*v[k] ;
     
    
   

    

     

    
    

     

       INT& best = dp[S^(1<<k)][j][k] ;
     
    
   

    

     

    
    

     
 if(best < mx)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       best = mx ;
     
    
   

    

     

    
    

     

       num[S^(1<<k)][j][k] = num[S][i][j] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else if(best == mx)
     
    
   

    

     

    
    

     

       num[S^(1<<k)][j][k] += num[S][i][j] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       INT sum = 0 ,ans = -1 ;
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(dp[(1<<n)-1][i][j] == -1) continue ;
     
    
   

    

     

    
    

     
 if(dp[(1<<n)-1][i][j] > ans)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       ans = dp[(1<<n)-1][i][j] ;
     
    
   

    

     

    
    

     

       sum = num[(1<<n)-1][i][j] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else if(dp[(1<<n)-1][i][j] == ans)
     
    
   

    

     

    
    

     

       sum += num[(1<<n)-1][i][j] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(sum)
     
    
   

    

     

    
    

     
 cout<<ans<<" "<<sum/2<<endl ;
     
    
   

    

     

    
    

     
 else   cout<<"0 0"<<endl ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       INT Tx ;
     
    
   

    

     

    
    

     
 scanf("%I64d",&Tx) ;
     
    
   

    

     

    
    

     
 while(Tx--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%I64d%I64d",&n,&m) ;
     
    
   

    

     

    
    

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

    

     

    
    

     
 scanf("%I64d",&v[i]) ;
     
    
   

    

     

    
    

     
 memset(w ,0 ,sizeof(w)) ;
     
    
   

    

     

    
    

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

    

     

    
    

     
 memset(num ,0 ,sizeof(num)) ;
     
    
   

    

     

    
    

     
 for(INT i = 0 ;i < m ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       INT x ,y ;
     
    
   

    

     

    
    

     
 scanf("%I64d%I64d",&x ,&y) ;
     
    
   

    

     

    
    

     

       x-- ; y-- ;
     
    
   

    

     

    
    

     

       w[x][y] = w[y][x] = 1 ;
     
    
   

    

     

    
    

     

       INT S = (1<<x) + (1<<y) ;//初始化两个点
     
    
   

    

     

    
    

     

       dp[S][x][y] = dp[S][y][x] = v[x] + v[y] + v[x]*v[y] ;
     
    
   

    

     

    
    

     

       num[S][x][y] = 1 ;
     
    
   

    

     

    
    

     

       num[S][y][x] = 1 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(n == 1) //特殊处理
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 cout<<v[0]<<" "<<1<<endl ;
     
    
   

    

     

    
    

     
 continue ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       DP() ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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