※ 引述《DJWS.bbs@ptt.cc (...)》之銘言：
: ※ 引述《sophialiege ()》之銘言：
: : 令[u,v]是正解
: : 就是最佳解的最低處高度是u,v是最高處
: : 因為每個格子的值在0~99之間,所以u和v也是在這之間
: : 對於每一組假設的[u,v],你可以在圖上將高度介於這之間的位置做記號
: : 看連通的記號足不足夠蓋一個部落
: : 再來是要降複雜度,假如[u,v]足夠蓋,那麼[u,v+k] (k 是正整數)
: : 也一定足夠 ==> bisch is possible
: : 故複雜度粗估是 Constant * 100 * 8 * 40 * 40
: : ^^^ ^^^ ^^^^^^^
: : u log(v) graph search
: 真神奇 原來可以這樣子來降低時間複雜度
: 我了解了 謝謝你 :)
: 另外再請教一件事情
: 我在討論版看到有人宣稱他使用了 union-find 來縮短時間 解決這一題
: 如果真是這樣 那要怎麼做呢?
我想應該是在"graph search"時他用union and find來進行分堆
這樣可以降掉一般搜尋的常數
--
※ 發信站: 批踢踢兔(ptt2.cc)
◆ From: 218.162.202.42