Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:关于1094的些想法

Posted by TurnAround at 2009-12-31 21:37:59 on Problem 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator