※ 引述《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
昨天沒有寫這題，不過看到這題的時候有一個很自然的猜想，
他給的值是在 node 上，如果能夠透過一些轉換 給予 edge 值，
跟著就直接做 MST ，做一步檢查一次每個subtree。
至於轉換的部份 假設 a, b 兩個 node 是連接的，
a[ 1 , 2] , b[ 3 , 4 ] 好了
那 edge(a, b) 的值為 (2 + 4) - (1 + 3) = 2
當時會這樣想的因素是希望 w 的和要盡量小 而 a 的和要盡量大。
不知道大家的看法是?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 60.248.4.140