好久沒寫程序練手了，今天本來準備拿POJ1025開刀的，但是1025這個模擬題目太
繁雜了，換一個，寫POJ1094，結果郁悶地寫了三個多小時——代碼水平有待提升呀。
下面是我寫這個題目的詳細過程，跟大家分享下：
題目地址：
http://acm.pku.edu.cn/JudgeOnline/problem?id=1094
題目描述：
一個升序串是一群用小于號連接起來的由小到大排列好的數(shù)值。例如，一個排好的序列 A, B, C, D 就表示 A < B, B < C 還有 C < D。現(xiàn)在，給你一堆格式為 A < B 的關系式給你，然后你就要去判斷有沒有一個可以排列的順序。
Input
輸入數(shù)據(jù)由多組測試數(shù)據(jù)組成。每一組測試數(shù)據(jù)的第一行是兩個整數(shù)n 和 m。 第一個整數(shù)代表有多少個字母要排列，而且 2 <= n <= 26。要排列的字母是大寫字母中的前n個。 第二個整數(shù)m表示會出現(xiàn)多少組像 A < B 這樣的數(shù)值關系。下面的m行，每一行有一個只有三個字符的關系式：一個大寫字母，符號“<”和另一個大寫字母。除了前n個大寫字母以外，不會其他字母字母。當 n = m = 0 時表示輸入結束。
Output
對應每組輸入數(shù)據(jù)，輸出只有一行。這一行要是以下三種情況之一：
Sorted sequence determined after xxx relations: yyy…y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.
xxx 就是當一個升序序列確定時或者發(fā)現(xiàn)有矛盾時所處理到的第幾個關系式，哪種情況先出現(xiàn)，就輸出哪種；而 yyy…y 就是排好序的升序序列。
××××××××××××××××××××××××××××××××××××××××××××××××××××××
下面是正題：
我拿到題目就認為這個題目的算法很簡單——不就拓撲排序嘛。但有一點比較關鍵：需要每輸入一個關系就判斷一次。不過總共的元素最多才26個，時間應該是夠用的。
然后就寫，很快寫完，過了樣例，檢查了一下，提交，WA,
兩個錯誤原因，一個是一條語句（見下面注釋）。
一個是沒有判斷環(huán)。
然后我就用DFS判斷環(huán)。
第二次得到TLE。
后面想了下DFS太慢，改進用矩陣判斷是否有回路。
第三次得到WA。.
然后重寫，還是WA。怎么回事？
然后看Discuss吧。
發(fā)現(xiàn)一組數(shù)據(jù)過不了
11 12
K<J
B<A
E<F
D<F
G<F
H<I
G<E
I<K
J<F
A<H
F<C
C<B
原來是矩陣更新寫錯了，再寫再交……
嗚嗚嗚，這回還是WA.
原來太急躁了，樣例都沒過——我把矩陣與元素之間得關系弄一起了，郁悶了。
然后再改吧。
這回沒有過，我還是發(fā)現(xiàn)了錯誤，
1 0
這一組都過不了。
改了再交，就是WA!!!???
終于找到了一句，每次排序后把元素的入度改了，
改好后交，還是WA.
原來沒有刪掉測試數(shù)據(jù)，太急躁了，BS下自己，這種錯誤不能有。
刪掉測試數(shù)據(jù)，終于AC了。
總結：
最后算法跟開始想的方向一樣，主要是具體實現(xiàn)有問題——而且都是細節(jié)，主要反映在對數(shù)據(jù)挖掘得不夠上。
自己很久沒寫代碼解題了，更加久沒寫圖論的題目了，現(xiàn)在考試只剩下專業(yè)課了，我可以適當放手開始寫代碼了——手生得厲害，我畢竟跟那些過分注重成績的人不是一樣的，還是做自己喜歡的事吧。
下面是代碼（很亂，加了我寫代碼的一系列過程中的調(diào)試注釋）：
1 /*********************************************************************
2 Author: littlekid
3 Created Time: 2008-1-11 11:49:58
4 Problem Source: POJ1094
5 Description:
47 ********************************************************************/
48
49 # include <iostream>
50 using namespace std;
51
52 const bool NOT_DETERMINE = true;
53 const bool FIND_INCONSISTENCY = true;
54
55 typedef struct node{
56 int in_degree;
57 int out_degree;
58 int out[ 27 ];
59 };
60
61 node elem[ 27 ];
62 int sequence[ 27 ];
63
64 int relation[ 27 ][ 27 ];
65
66 void test( int n )
67 {
68 for ( int i = 0; i < n; i ++ )
69 {
70 for ( int j = 0; j < n; j ++ )
71 {
72 printf( "%d ", relation[ i ][ j ] );
73 }
74 printf( "\n" );
75 }
76 }
77
78 void output( bool flag )
79 {
80 printf( "Sorted sequence cannot be determined.\n" );
81 }
82
83 void output( bool flag, int no )
84 {
85 printf( "Inconsistency found after %d relations.\n", no );
86 }
87
88 void output_relation_ship( int n )
89 {
90 for ( int i = 0; i < n; i ++ )
91 {
92 printf( "%c", sequence[ i ]+'A' );
93 }
94 }
95
96 void output( int no, int n )
97 {
98 printf( "Sorted sequence determined after %d relations: ", no );
99 output_relation_ship( n );
100 printf( ".\n" );
101 }
102
103 void add_relation_ship( int a, int b, int n )
104 {
105 //elem[ a ].out_degree ++;//The first edition come up WA because of this sentence
106 elem[ b ].in_degree ++;
107
108 elem[ a ].out[ elem[ a ].out_degree ++ ] = b;
109
110 relation[ a ][ b ] = 1;
111 for ( int i = 0; i < n; i ++ ) ///
112 {
113 for ( int j = 0; j < n; j ++ )
114 {
115 for ( int k = 0; k < n; k ++ )
116 {
117 if ( relation[ i ][ k ] && relation[ k ][ j ] )
118 {
119 relation[ i ][ j ] = 1;
120 }
121 }
122 }
123 }
124 }
125 /*
126 bool have_visited[ 27 ];
127 int color[ 27 ];
128
129 int DFS( int now )
130 {
131 if ( have_visited[ now ] )
132 {
133 return 1;
134 }
135 have_visited[ now ] = true;
136 color[ now ] = 1;
137 for ( int i = 0; i < elem[ now ].out_degree; i ++ )
138 {
139 if ( DFS( elem[ now ].out[ i ] ) == 1 ) return 1;
140 }
141 have_visited[ now ] = false;
142 return 0;
143 }
144
145
146 int has_circle( int n )
147 {
148 memset( color, 0, sizeof( color ));
149 memset( have_visited, false, sizeof( have_visited ) );
150 for ( int i = 0; i < n; i ++ )
151 {
152 if ( !color[ i ] )
153 if ( DFS( i ) == 1 ) return -1;
154 }
155 return 0;
156 }
157 */
158
159 int has_circle( int n )
160 {
161 for ( int i = 0; i < n; i ++ )
162 {
163 if ( relation[ i ][ i ] ) return -1;
164 }
165 return 0;
166 }
167
168 int top_sort( int n )
169 {
170 int cur;
171 int tot = 0;
172 bool select[ n ];
173 memset( select, false, sizeof( select ));
174 int indegree[ 27 ];
175 for ( int i = 0; i < n; i ++ )
176 {
177 indegree[ i ] = elem[ i ].in_degree;
178 }
179
180 while ( tot < n )
181 {
182 cur = -1;
183 for ( int i = 0; i < n; i ++ )
184 {
185 if ( indegree[ i ] == 0 && !select[ i ] )
186 {
187 if ( cur != -1 )
188 {
189 return has_circle( n );
190 }
191 cur = i;
192 }
193 }
194
195 if ( cur == -1 )
196 {
197 return -1; //
198 }
199 //printf( "--%d\n", cur );
200 sequence[ tot++ ] = cur;
201 select[ cur ] = true;
202 for ( int i = 0; i < elem[ cur ].out_degree; i ++ )
203 {
204 //elem[ elem[ cur ].out[ i ] ].in_degree --; // 最后發(fā)現(xiàn)這一句錯了！！
205 indegree[ elem[ cur ].out[ i ] ] --;
206 }
207 }
208 return 1;
209 }
210
211 void solve( int n, int m )
212 {
213 char s[ 5 ];
214 int result;
215 bool not_determine = true;
216
217 if ( n == 1 )
218 {
219 sequence[ 0 ] = 0;
220 output( 0, n );
221 not_determine = false;
222 }
223
224 for ( int i = 1; i <= m; i ++ )
225 {
226 scanf( "%s", &s );
227 if ( not_determine )
228 {
229 add_relation_ship( s[0]-'A', s[2]-'A', n );
230 result = top_sort( n );
231 if ( result == 1 )
232 {
233 output( i, n );
234 not_determine = false;
235 }
236 else if ( result == -1 )
237 {
238 output( FIND_INCONSISTENCY, i );
239 not_determine = false;
240 }
241 }
242 }
243
244 if ( not_determine )
245 {
246 output( NOT_DETERMINE );
247 }
248 }
249
250 void initialize( int n )
251 {
252 memset( relation, 0, sizeof( relation ) );
253 for ( int i = 0; i < n; i ++ )
254 {
255 elem[ i ].in_degree = 0;
256 elem[ i ].out_degree = 0;
257 }
258 }
259
260 int main()
261 {
262 int n, m;
263 while ( true )
264 {
265 scanf( "%d %d", &n, &m );
266 if ( n == 0 && m == 0 ) break;
267 initialize( n );
268 solve( n,m );
269 // test( n );
270 }
271 return 0;
272 }
273
posted on 2008-01-11 15:27
R2 閱讀(1748)
評論(5) 編輯 收藏 引用 所屬分類:
Problem Solving