[問題] PA3 的 output 值 victoret PTT批踢踢實業坊

[問題] PA3 的 output 值

作者: victoret (戲言~) 2012-05-05 23:27:34

跟之前一樣...做完大的 case...
看到一堆 edge 和大的可怕的 total_weight...還是毛毛的 XD
就 PO 一下結果看看跟大家的一不一樣 @@
BFS（雖然說 total_weight 沒什麼意義...不過應該是唯一吧？）
gn50000
Source node：v0 total_weight：2478895
Source node：v24999 total_weight：2470628
Source node：v49999 total_weight：2476565
DFS
gn50000
Source node：0 total_weight：2478177
Source node：24999 total_weight：2468755
Source node：49999 total_weight：2478154
MST
gn4 total_weight：6
gn10 total_weight：416
gn100 total_weight：1438
gn1000 total_weight：18927
gn10000 total_weight：189642
gn50000 total_weight：930795
然後 MST 執行的時間是
gn10000：0.333852 s
gn50000：14.9361 s
請問這個速度會不會太慢 @@
謝謝！

作者: craig08 (小佑) 2012-05-05 23:57:00

total_weight都一樣 10000:0.6s 50000:7s

作者: anfranion (å—â€§ç”Ÿå‘½çš„æ„ç¾©æ˜¯ç¶“æ·) 2012-05-06 00:23:00

我的weight也都一樣~ 不過因為我加了minHeap-O2下time 50000的是0.2s, 10000的是0.1s 其他就~=0s

作者: victoret (戲言~) 2012-05-06 09:34:00

感謝樓上兩位！

作者: djshen (djshen) 2012-05-06 14:16:00

mst 50000 0.1s 10000 0.03s weight都一樣

作者: kkrrkk100 (說什麼都是多餘) 2012-05-07 03:15:00

我的慢到掉渣= =

作者: ypf791 (路人1號) 2012-05-07 14:27:00

mst 50000 0.2s 10000 0.04s weight都一樣我怎麼會以為自己可能比djshen快...

作者: djshen (djshen) 2012-05-07 15:17:00

已經夠快了吧= =

繼續閱讀

Re: [問題] is spanning treerf0914 Re: [問題] output順序Usoul [問題] 關於PA3的input formatkkrrkk100 [公告] PA3繳交規定Usoul [分享] hw3的題目(pdf)anfranion [問題] 指令option的順序QQvei [問題] dfszeroshine [問題] 關於vertex的名字OckhamsRazor [問題] output順序craig08 [問題] is spanning treewintercobra