Re: [問題] 樹上路徑和為 k
看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間9年前 (2015/03/03 03:48)推噓1(1推 0噓 1→)留言2則, 2人參與討論串2/3 (看更多)
: 輸入：一個 n 個頂點的樹 T，每一個頂點 v 有一個整數權重 w(v)，及一整數 k。
: 輸出：一條 T 上的路徑（任意起點終點），其路徑上頂點權重的總和為 k 。
: 推 DJWS: 能不能推薦幾篇centroid/spine decomposition的教學資料? 03/02 08:14
http://wenku.baidu.com/view/60c6aa1ffc4ffe473368aba8.html
這個有介紹一下 centroid decomposition。
http://www.cnblogs.com/xiao_wu/archive/2010/06/01/1748728.html
一些相關問題
http://fanhq666.blog.163.com/blog/static/81943426201172472943638/
動態情況
我認真的搜尋了一下，我問的問題有出現在 zoj 2304 / poj 2114 Boatherds
http://blog.sina.com.cn/s/blog_5123df35010098vr.html
IOI 2011 也有這題
http://www.ioi2011.or.th/hsc/tasks/solutions/race.pdf
BZOJ 1758 是找出樹上 length constrainted 的 maximum density path
https://www.byvoid.com/blog/wc2010-rebuild
網路上看的作法是O(n lg n lg RANGE)
理論上是可以做到O(n lg n) （spine decomposition）
可以參考 An optimal algorithm for the maximum-density path in a tree
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 129.170.195.149
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1425325700.A.947.html
推
03/03 09:01, , 1F
03/03 09:01, 1F
※ 編輯: FRAXIS (129.170.195.149), 03/04/2015 00:57:55
→
03/04 00:58, , 2F
03/04 00:58, 2F
※ 編輯: FRAXIS (129.170.195.149), 03/04/2015 22:21:22
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
-4
30