Detail of message

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

btw，并查集加启发式合并能快多少？我向来是只路径压缩~

Posted by palmtenor at 2005-06-08 11:16:58 on Problem 1182
In Reply To:你超时是算法不对吧？和数据没关系，不过你非要说数据卡你的算法就没办法了 Posted by:frkstyc at 2005-06-08 10:58:17

Followed by:

没试过，我的disjoint set模版向来都是两个优化都有的 (0) frkstyc 2005-06-08 11:25:12
- 无语，这个题去掉启发合并之后……更快了 (0) frkstyc 2005-06-08 11:32:48
  - 那到底还要不要启发合并？ (0) frkstyc 2005-06-08 11:35:33
    - 这个题能启发式合并吗？我怎么觉得启发以后就WA了。。。 (0) js05 2005-06-08 11:52:39
      - 记错了，这个题是可以启发式合并的。。。 (0) js05 2005-06-08 11:54:35
        ft (0) frkstyc 2005-06-08 11:54:46
  - 其实我觉得启发合并对于大多数disjoint set的题来讲没有什么用.....效果实在太小了~ (0) palmtenor 2005-06-08 13:10:53
    - 用递归写的disjoint set,按秩合并效果...貌似不大 (0) ArXoR 2005-06-08 13:43:29
      - ？？？？disjoint set怎么递归？？？ (0) frkstyc 2005-06-08 13:44:29
        就是findroot那种,一次性接到根 (0) ArXoR 2005-06-08 13:45:09
        哦，我写了一个栈来搞 (0) frkstyc 2005-06-08 13:45:35
        栈，并查集威为什么要用这个东西。。。 (0) js05 2005-06-08 14:00:04
        因为styc这个人比较BT，习惯于干消递归或者asm code这种无聊事情...... (0) palmtenor 2005-06-08 14:02:09
        可是这里不需要递归，也不需要栈嘛。。。 (0) js05 2005-06-08 14:04:09
        那你的find-set怎么做的？ (0) 00448264 2005-06-08 14:06:02
        从底下往上找，压缩的时候在找一次就好了。。。 (0) js05 2005-06-08 14:07:31
        我是在find的同时压缩路径 (0) frkstyc 2005-06-08 14:10:32
        哦，理解了。。。 (0) js05 2005-06-08 14:11:48
        life is too long for you... (0) 00448264 2005-06-08 14:05:39

Post your reply here:

Home Page Go Back To top

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