HDU 1518题 Square （DFS）

题目链接~~>

                   刚刚开始深入研究一下深搜，不料，其实这题也不难，只是没深入思考。。只需要一个小剪枝就行。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      int g[22] ;
     
    
   

    

     

    
    

     

      int n,mx,f ;
     
    
   

    

     

    
    

     

      void dfs(int sm,int q,int cnt)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int i,t ;
     
    
   

    

     

    
    

     
 if(f||q==3)//只需要找到3个边就行。
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       f=1 ;
     
    
   

    

     

    
    

     
 return ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for(i=cnt;i<n;i++)//cnt很重要！！避免1-2-3和1-3-2等的重复。。。
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(g[i]&&g[i]+sm<mx)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       t=g[i] ;
     
    
   

    

     

    
    

     

       g[i]=0 ;
     
    
   

    

     

    
    

     

       dfs(t+sm,q,i+1) ;
     
    
   

    

     

    
    

     

       g[i]=t ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else if(g[i]&&g[i]+sm==mx)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       sm=0 ;
     
    
   

    

     

    
    

     

       t=g[i] ;
     
    
   

    

     

    
    

     

       g[i]=0 ;
     
    
   

    

     

    
    

     

       dfs(0,q+1,0) ;//不要忘记标记g[i]=0 ；
     
    
   

    

     

    
    

     

       g[i]=t ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int T,i ;
     
    
   

    

     

    
    

     
 scanf("%d",&T) ;
     
    
   

    

     

    
    

     
 while(T--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%d",&n) ;
     
    
   

    

     

    
    

     
 int sum=0 ;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

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

    

     

    
    

     

       sum+=g[i] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(sum%4==0)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       mx=sum/4 ;f=0 ;
     
    
   

    

     

    
    

     

       dfs(0,0,0) ;
     
    
   

    

     

    
    

     
 if(f)
     
    
   

    

     

    
    

     
 printf("yes\n") ;
     
    
   

    

     

    
    

     
 else printf("no\n") ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 else printf("no\n") ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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