看板 [ Prob_Solve ]
討論串[問題] 樹上路徑和為 k
共 3 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] 樹上路徑和為 k
推噓4(4推 0噓 8→)留言12則，0人參與, 最新作者FRAXIS (喔喔)時間9年前 (2015/03/02 00:24), 編輯資訊
1
0
1
內容預覽:
輸入：一個 n 個頂點的樹 T，每一個頂點 v 有一個整數權重 w(v)，及一整數 k。. 輸出：一條 T 上的路徑（任意起點終點），其路徑上頂點權重的總和為 k 。. 這問題應該可以用O(n lg n)解出來，只是需要用centroid decomposition. 或是 spine decomp
(還有124個字)
#2
Re: [問題] 樹上路徑和為 k
推噓1(1推 0噓 1→)留言2則，0人參與, 最新作者FRAXIS (喔喔)時間9年前 (2015/03/03 03:48), 9年前編輯資訊
0
0
6
內容預覽:
http://wenku.baidu.com/view/60c6aa1ffc4ffe473368aba8.html. 這個有介紹一下 centroid decomposition。. http://www.cnblogs.com/xiao_wu/archive/2010/06/01/1748728.
(還有561個字)
#3
Re: [問題] 樹上路徑和為 k
推噓0(0推 0噓 1→)留言1則，0人參與, 最新作者FRAXIS (喔喔)時間9年前 (2015/03/05 03:08), 9年前編輯資訊
0
0
0
內容預覽:
就我有限的理解，我說明一下 spine decomposition ，大家可以討論。. 首先考慮一個簡單的問題. 輸入： 一條 n 個點的路徑，邊上有權重及長度（可正可負），以及一數字 U 。. 輸出： 長度和小於 U 子路徑中，最大的權重和。. 這問題跟 maximum sum subarray
(還有932個字)
首頁
上一頁
1
下一頁
尾頁