May the force be with you!
posts - 52,  comments - 33,  trackbacks - 0

      好久没写程序练手了,今天本来准备拿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 阅读(1688) 评论(5)  编辑 收藏 引用 所属分类: Problem Solving

FeedBack:
# re: 【解题回顾】我写poj1094的过程
2008-01-11 16:43 | <a href=http://minidx.com>minidxer</a>
的确是乱了点,不过还好,可以看明白~
  回复  更多评论
  
# re: 【解题回顾】我写poj1094的过程
2008-01-11 21:46 | winsty
# re: 【解题回顾】我写poj1094的过程
2008-01-11 22:02 | littlekid
嗯,代码由整理过的好的版本,
之所以把这么乱的代码贴上来是为了体现做题过程。  回复  更多评论
  
# re: 【解题回顾】我写poj1094的过程
2008-01-11 22:14 | Ocean@whuacm
@winsty
这个代码确实需要优化,你的代码值得学习,然后就是那个Floyed的方法肯定很好玩~~  回复  更多评论
  
# re: 【Toplogical Sort】【解题回顾】我写poj1094的过程
2009-07-18 16:02 | 爱YST
195 if ( cur == -1 )
196 {
197 return -1; //
198 }
199 //printf( "--%d\n", cur );

top_sort这句代码可以省去的,上面的has_circle能将环测试出来并返回值。  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


你是第 free hit counter 位访客




<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(4)

随笔分类(54)

随笔档案(52)

文章档案(1)

ACM/ICPC

技术综合

最新随笔

搜索

  •  

积分与排名

  • 积分 - 61526
  • 排名 - 357

最新评论

阅读排行榜

评论排行榜