※ 引述《sophialiege ()》之銘言：
: 題目: 給定一個 undirected tree T, T 每個 node 有兩個 attribute [a,w]
: a是整數,w是正整數
: 另給兩個正整數Wmin和Wmax 1<= Wmin, Wmax <=10000
: 要求: 找出一個T的subtree T',使得 floor(T'內的a總合/T'內的w總合) 要最大
: 且T'內的w總和要 >=Wmin <=Wmax
我的想法是先隨意pick一個node當root
考慮optimal solution包不包含root的情況
不包含就變成更小的問題,因為被root斷開的任意兩subset不可能不經root而形成tree
包含就有點像list的方法解下去 <= 這一步不太清楚要怎麼做
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.250.175