Posted on 2008-08-19 21:16
Hero 閱讀(192)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 //Accepted 2193 C++ 00:00.00 392K
2 //2585 Accepted 208K 0MS C++ 1883B
3
4 //拓撲排序--與層有關的大部分是拓撲排序
5
6 #include <stdio.h>
7 #include <stdlib.h>
8 #include <string.h>
9
10 char instr[50] ;
11
12 int data[10][10] ;
13 int edge[10][10] ;
14 int indeg[20] ;
15 int toporder[150] ;
16 int ctop ;
17
18 void input()
19 {
20 for( int i=1; i<=4; i++ ) for( int j=1;j<=4; j++ )
21 scanf( "%d", &data[i][j] ) ;
22 scanf( "%s", instr ) ;
23 }
24
25
26 int Topsort( int inn )//inn--點的數目
27 {//用棧輸出單一拓撲排序
28
29 memset( indeg, 0, sizeof(indeg) ) ;
30 for( int sn=1; sn<=inn; sn++ ) {
31 for( int en=1; en<=inn; en++ ) {
32 if( edge[en][sn] ) indeg[sn]++ ;
33 }
34 }
35 int stack[150] ; int top = -1 ;
36 for( int i=1; i<=inn; i++ ) {
37 if( 0 == indeg[i] ) stack[++top] = i ;
38 }//建立入度為0的棧stack[]
39
40 int cnt_node = 0 ; ctop = -1 ;
41 while( top >= 0 )
42 {
43 //printf( "%d\n", stack[top] ) ;
44 int curnode = stack[top--] ; //indeg[curnode] = -1 ;//容易忘記
45 toporder[++ctop] = curnode ; cnt_node++ ;
46
47 for( int j=1; j<=inn; j++ )
48 {
49 if( edge[curnode][j] )
50 {
51 indeg[j]-- ;
52 if( 0 == indeg[j] ) stack[++top] = j ;
53 }//不要忘了加大括號--WA了好多
54 }
55 }
56
57 if( cnt_node < inn ) { /*printf( "Topsort error--cycle!\n" ) ;*/ return 0 ; }
58
59 return 1 ;
60 }
61
62 void process()
63 {
64 memset( edge, 0, sizeof(edge) ) ;
65
66 for( int i=1; i<=3; i++ ) {
67 for( int j=1; j<=3; j++ ) {
68 int val = ( i-1 ) * 3 + j ;
69 if( data[i][j] != val ) edge[val][data[i][j]] = 1 ;
70 if( data[i][j+1] != val ) edge[val][data[i][j+1]] = 1 ;
71 if( data[i+1][j] != val ) edge[val][data[i+1][j]] = 1 ;
72 if( data[i+1][j+1] != val ) edge[val][data[i+1][j+1]] = 1 ;
73 }
74 }//建圖
75
76 int topval = Topsort( 9 ) ;
77 if( topval ) printf( "THESE WINDOWS ARE CLEAN\n" ) ;
78 else printf( "THESE WINDOWS ARE BROKEN\n" ) ;
79 }
80
81 int main()
82 {
83 while( scanf( "%s", instr ) != EOF )
84 {
85 if( 0 == strcmp( instr, "ENDOFINPUT" ) ) break ;
86
87 input() ;
88
89 process() ;
90
91 //output() ;
92 }
93
94 return 0 ;
95 }