UVA-116 - Unidirectional TSP

题目链接~~>

做题感悟：因为做DAG的缘故，开始便用记忆化去写，结果超时，只好改为动态规划的递推的形式，但是还是写的挺麻烦。

解题思路：

        （1）、动态规划递推完之后，用递归的方法输出字典序的路径。

         （2）、动态规划的过程中不断记录行值（按字典序记录），最后for 输出即可。

代码（本人）：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #define INT long long int
     
    
   

    

     

    
    

     

      const int INF = 99999999 ;
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const int MX = 1000 + 10 ;
     
    
   

    

     

    
    

     

      int n ,m,ans ;
     
    
   

    

     

    
    

     

      bool first ;
     
    
   

    

     

    
    

     

      int g[MX][MX],a[MX][MX] ;
     
    
   

    

     

    
    

     

      void DP()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
   for(int j=m-2 ;j>=0 ;j--)
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int mx=INF ;
     
    
   

    

     

    
    

     
 if(i==0)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(g[i][j+1]<mx)
     
    
   

    

     

    
    

     

       mx=g[i][j+1] ;
     
    
   

    

     

    
    

     
 if(g[i+1][j+1]<mx&&i+1<n)
     
    
   

    

     

    
    

     

       mx=g[i+1][j+1] ;
     
    
   

    

     

    
    

     
 if(g[n-1][j+1]<mx)
     
    
   

    

     

    
    

     

       mx=g[n-1][j+1] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else if(i==n-1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(g[0][j+1]<mx)
     
    
   

    

     

    
    

     

       mx=g[0][j+1] ;
     
    
   

    

     

    
    

     
 if(g[i-1][j+1]<mx&&i-1>=0)
     
    
   

    

     

    
    

     

       mx=g[i-1][j+1] ;
     
    
   

    

     

    
    

     
 if(g[i][j+1]<mx)
     
    
   

    

     

    
    

     

       mx=g[i][j+1] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(g[i-1][j+1]<mx&&i-1>=0)
     
    
   

    

     

    
    

     

       mx=g[i-1][j+1] ;
     
    
   

    

     

    
    

     
 if(g[i][j+1]<mx)
     
    
   

    

     

    
    

     

       mx=g[i][j+1] ;
     
    
   

    

     

    
    

     
 if(g[i+1][j+1]<mx&&i+1<n)
     
    
   

    

     

    
    

     

       mx=g[i+1][j+1] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       g[i][j]+=mx ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void print(int x,int y)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(first)   first=false,cout<<x+1 ;
     
    
   

    

     

    
    

     
 else cout<<" "<<x+1 ;
     
    
   

    

     

    
    

     
 if(y==m-1)  return ;
     
    
   

    

     

    
    

     
 int  ans=g[x][y]-a[x][y] ;
     
    
   

    

     

    
    

     
 if(!x)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(ans==g[x][y+1])
     
    
   

    

     

    
    

     

       print(x,y+1) ;
     
    
   

    

     

    
    

     
 else if(ans==g[x+1][y+1]&&x+1<n)
     
    
   

    

     

    
    

     

       print(x+1,y+1) ;
     
    
   

    

     

    
    

     
 else if(ans==g[n-1][y+1])
     
    
   

    

     

    
    

     

       print(n-1,y+1) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else if(x==n-1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(ans==g[0][y+1])
     
    
   

    

     

    
    

     

       print(0,y+1) ;
     
    
   

    

     

    
    

     
 else if(ans==g[x-1][y+1]&&x-1>=0)
     
    
   

    

     

    
    

     

       print(x-1,y+1) ;
     
    
   

    

     

    
    

     
 else if(ans==g[x][y+1])
     
    
   

    

     

    
    

     

       print(x,y+1) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(ans==g[x-1][y+1]&&x-1>=0)
     
    
   

    

     

    
    

     

       print(x-1,y+1) ;
     
    
   

    

     

    
    

     
 else if(ans==g[x][y+1])
     
    
   

    

     

    
    

     

       print(x,y+1) ;
     
    
   

    

     

    
    

     
 else if(ans==g[x+1][y+1]&&x+1<n)
     
    
   

    

     

    
    

     

       print(x+1,y+1) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       first=true ;
     
    
   

    

     

    
    

     

       ans=INF ;
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

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

    

     

    
    

     

       a[i][j]=g[i][j] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       DP() ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<n ;i++) // 寻找最大值
     
    
   

    

     

    
    

     
 if(ans>g[i][0])
     
    
   

    

     

    
    

     

       ans=g[i][0] ;
     
    
   

    

     

    
    

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

    

     

    
    

     
 if(g[i][0]==ans)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       print(i,0) ;
     
    
   

    

     

    
    

     
 break ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 printf("\n") ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

优代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #define INT long long int
     
    
   

    

     

    
    

     

      const int INF = 99999999 ;
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const int MX = 1000 + 10 ;
     
    
   

    

     

    
    

     

      int n ,m ;
     
    
   

    

     

    
    

     

      int g[MX][MX],d[MX][MX] ;
     
    
   

    

     

    
    

     

      void DP()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
   for(int i=m-2 ;i>=0 ;i--)
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int *p=&g[i+1][0] ;
     
    
   

    

     

    
    

     
 int Min=(j+1)%n,dn=(j-1+n)%n ;
     
    
   

    

     

    
    

     
 if(p[j]<p[Min]||(p[j]==p[Min]&&j<Min))
     
    
   

    

     

    
    

     

       Min=j ;
     
    
   

    

     

    
    

     
 if(p[dn]<p[Min]||(p[dn]==p[Min]&&dn<Min))
     
    
   

    

     

    
    

     

       Min=dn ;
     
    
   

    

     

    
    

     

       g[i][j]+=p[Min] ;
     
    
   

    

     

    
    

     

       d[i][j]=Min ; // 记录上一步行值
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void print(int mx)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
   cout<<mx+1 ;
     
    
   

    

     

    
    

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

    

     

    
    

     

         {
     
    
   

    

     

    
    

     

       mx=d[i-1][mx] ;
     
    
   

    

     

    
    

     
 cout<<" "<<mx+1 ;
     
    
   

    

     

    
    

     

         }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     

       DP() ;
     
    
   

    

     

    
    

     
 int mx = min_element(&g[0][0],&g[0][n])-&g[0][0] ; // 寻找第一行最小元素下标
     
    
   

    

     

    
    

     
 int ans=g[0][mx] ;
     
    
   

    

     

    
    

     

       print(mx) ; // 输出
     
    
   

    

     

    
    

     
 cout<<endl<<ans<<endl ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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