作者appleway (apple)
看板ACMCLUB
标题Re: 问一下昨天的problem J
时间Sun Oct 16 12:18:16 2005
※ 引述《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