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