HDu 4380 Farmer Greedy(複数校3)

8339 ワード

http://acm.hdu.edu.cn/showproblem.php?pid=4380
交錯している間に穴が開いたような感じがしてトポロジーが水を渡ったとは思わなかった.


View Code
 1 #include <iostream>

 2 #include<cstdio>

 3 #include<string.h>

 4 using namespace std;

 5 int de[2001];

 6 char c[2001][2001];

 7 int main()

 8 {

 9     int i,j,t,n,m,f,k,kk =0;

10     scanf("%d",&t);

11     while(t--)

12     {

13         memset(de,0,sizeof(de));

14         kk++;

15         scanf("%d",&n);

16         int flag = 1;

17         for(i = 1; i <= n ; i++)

18         {

19             getchar();

20             for(j = 1; j <= n; j++)

21             {

22                 c[i][j] = getchar();

23                 if(c[i][j] == '1')

24                 de[j]++;

25             }

26         }

27         for(i = 1; i <= n ;i++)

28         {

29             f = 0;

30             for(j = 1; j <= n ; j++)

31             {

32                 if(de[j]==0)

33                 {

34                     f = 1;

35                     de[j] = -1;

36                     for(k = 1; k <= n ; k++)

37                     if(c[j][k]=='1')

38                     de[k]--;

39                     break;

40                 }

41             }

42             if(!f)

43             {

44                 flag = 0;

45                 break;

46             }

47         }

48         printf("Case #%d: ",kk);

49         if(!flag)

50         printf("Yes
"); 51 else 52 printf("No
"); 53 } 54 return 0; 55 }