好久沒寫程序練手了，今天本來準備拿POJ1025開刀的，但是1025這個模擬題目太
繁雜了，換一個，寫POJ1094，結果郁悶地寫了三個多小時——代碼水平有待提升呀。
下面是我寫這個題目的詳細過程，跟大家分享下：
題目地址：
http://acm.pku.edu.cn/JudgeOnline/problem?id=1094
題目描述：
一個升序串是一群用小于號連接起來的由小到大排列好的數值。例如，一個排好的序列 A, B, C, D 就表示 A < B, B < C 還有 C < D。現在，給你一堆格式為 A < B 的關系式給你，然后你就要去判斷有沒有一個可以排列的順序。
Input
輸入數據由多組測試數據組成。每一組測試數據的第一行是兩個整數n 和 m。 第一個整數代表有多少個字母要排列，而且 2 <= n <= 26。要排列的字母是大寫字母中的前n個。 第二個整數m表示會出現多少組像 A < B 這樣的數值關系。下面的m行，每一行有一個只有三個字符的關系式：一個大寫字母，符號“<”和另一個大寫字母。除了前n個大寫字母以外，不會其他字母字母。當 n = m = 0 時表示輸入結束。
Output
對應每組輸入數據，輸出只有一行。這一行要是以下三種情況之一：
Sorted sequence determined after xxx relations: yyy…y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.
xxx 就是當一個升序序列確定時或者發現有矛盾時所處理到的第幾個關系式，哪種情況先出現，就輸出哪種；而 yyy…y 就是排好序的升序序列。
××××××××××××××××××××××××××××××××××××××××××××××××××××××
下面是正題：
我拿到題目就認為這個題目的算法很簡單——不就拓撲排序嘛。但有一點比較關鍵：需要每輸入一個關系就判斷一次。不過總共的元素最多才26個，時間應該是夠用的。
然后就寫，很快寫完，過了樣例，檢查了一下，提交，WA,
兩個錯誤原因，一個是一條語句（見下面注釋）。
一個是沒有判斷環。
然后我就用DFS判斷環。
第二次得到TLE。
后面想了下DFS太慢，改進用矩陣判斷是否有回路。
第三次得到WA。.
然后重寫，還是WA。怎么回事？
然后看Discuss吧。
發現一組數據過不了
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.
原來太急躁了，樣例都沒過——我把矩陣與元素之間得關系弄一起了，郁悶了。
然后再改吧。
這回沒有過，我還是發現了錯誤，
1 0
這一組都過不了。
改了再交，就是WA!!!???
終于找到了一句，每次排序后把元素的入度改了，
改好后交，還是WA.
原來沒有刪掉測試數據，太急躁了，BS下自己，這種錯誤不能有。
刪掉測試數據，終于AC了。
總結：
最后算法跟開始想的方向一樣，主要是具體實現有問題——而且都是細節，主要反映在對數據挖掘得不夠上。
自己很久沒寫代碼解題了，更加久沒寫圖論的題目了，現在考試只剩下專業課了，我可以適當放手開始寫代碼了——手生得厲害，我畢竟跟那些過分注重成績的人不是一樣的，還是做自己喜歡的事吧。
下面是代碼（很亂，加了我寫代碼的一系列過程中的調試注釋）：
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 --; // 最后發現這一句錯了！！
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