HDu 4380 Farmer Greedy(複数校3)
8339 ワード
http://acm.hdu.edu.cn/showproblem.php?pid=4380
交錯している間に穴が開いたような感じがしてトポロジーが水を渡ったとは思わなかった.
View Code
交錯している間に穴が開いたような感じがしてトポロジーが水を渡ったとは思わなかった.
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 }