作者sophialiege ()
看板ACMCLUB
标题Re: 问一下昨天的problem J
时间Sun Oct 16 08:42:17 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
我的想法是先随意pick一个node当root
考虑optimal solution包不包含root的情况
不包含就变成更小的问题,因为被root断开的任意两subset不可能不经root而形成tree
包含就有点像list的方法解下去 <= 这一步不太清楚要怎麽做
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.250.175