HDU 4324题Triangle LOVE(拓扑排序)

题目链接~~> 

     刚学习了拓扑排序就拿这个题试了一试，结果。。。。开始时居然用了两个for循环加个scanf("%d",&g[i][j]),晕死啊！！！解决了这个后很快写完，也很快TLE了！想来老半天剪枝但是这题真没法剪。。。。最后参考了一下别人代码只有在输入时的scanf("%s",g[i]);不同~~~改了后AC，无语。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      int topo[2003],n;
     
    
   

    

     

    
    

     

      char g[2002][2003];
     
    
   

    

     

    
    

     

      int toposort()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int f=0;
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       f=0;
     
    
   

    

     

    
    

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

    

     

    
    

     
 if(topo[j]==0)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       f=1;
     
    
   

    

     

    
    

     

       topo[j]=-1;
     
    
   

    

     

    
    

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

    

     

    
    

     
 if(g[j][k]=='1')
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       topo[k]--;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 break;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(f==0)
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 1;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int q=1,T,i,j;
     
    
   

    

     

    
    

     
 scanf("%d",&T);
     
    
   

    

     

    
    

     
 while(T--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 memset(topo,0,sizeof(topo));
     
    
   

    

     

    
    

     
 scanf("%d",&n);
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%s",g[i]);
     
    
   

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(g[i][j]=='1')
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       topo[j]++;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(toposort())
     
    
   

    

     

    
    

     
 printf("Case #%d: No\n",q++);
     
    
   

    

     

    
    

     
 else
     
    
   

    

     

    
    

     
 printf("Case #%d: Yes\n",q++);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

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

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