Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:关于1094的些想法In Reply To:关于1094的些想法 Posted by:20071002871 at 2009-04-11 10:46:42 没想到还可以这样做,太牛了,ORZ.. ----------------- > 昨天POJ挂了,在zoj 1060做这题,wa了n次,火了,很早就去睡觉了。终于找出了错误,输出的序列并不是唯一的,如 > 3 2 > C<A > A<B > 就应该是C<A<B,但我误以为每次处理到可以找出这样一个序列时,一定是A<B<C,思维惯性。 > 用求传递闭包的方法做的,每次加入1条边动态的更新,每次更新复杂度为O(n^2),故总复杂度为m*n*n。 > 更新每一条边时 > map[s][t]=1; > for(i=1;i<=n;++i) > for(j=1;j<=n;++j) > if(i!=s&&t!=j) > map[i][j]=map[i][j]||(map[i][s]&&map[t][j]); > else if(i==s&&t!=j) > map[i][j]=map[i][j]||map[t][j]; > else if(i!=s&&t==j) > map[i][j]=map[i][j]||map[i][s]; > 我的默认为map[i][i]是为0的,而如果存在环的话,则必定有个点自己可以到自己即map[i][i]=1,如果存在1个满足条件的序列的话,那么每个点的入度和出度之和必定等于n-1, > 如果这n个点都满足条件,那么就可以将其保存下来,后面不再更新了。 > 如3660那题一样。。。,最终OMS,但用拓补排序,也不能很好的利用上次排序的结果吧, > 好像只能又重新再拓补一次,复杂度未必比求传递闭包好。打算改用拓补排序试一下。。 > 以上为我的想法,忘指正,特别是拓补排序那儿,是否是我想错了,有好的方法请指出,谢谢。。。 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator