※ 引述《[email protected] (...)》之銘言： : ※ 引述《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