学步园

题目链接~~>

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

代码：

#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 ;
}