http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1496. bomb(高胜寒)
时间限制:2.0s   内存限制:256.0MB  
总提交次数:142   AC次数:18   平均分:45.35
将本题分享到:
   
 
问题描述
  S国正在进行核武器试验,数以亿计的科学家们前来观测。试验区位于S国某城市,此城市有n个区域,共有n-1条道路连接它们,任意两片区域可相互到达。其中核弹将于某个区域引爆,科学家们将去往一些度数为1的非引爆点区域,即观测点观察。抽象的说,若将此引爆区域设为有根树的根,科学家们将去往非根叶子节点。所有科学家可以同时行动,每条道路双向通行,且均给出一个所需通过的时间,然而每个观测点容纳人数有限,但是保证观测点容量大于等于科学家数。求科学家们最少所需移动时间,以使试验尽早开始。
输入格式
  第一行输入一个正整数n,表示点的数量,接下来n行,每行一条描述。
  第i+1行第一个数字ai,表示i号节点的儿子数。接下来2ai个数,第2j-1个数bij表示i号节点的孩子,第2j个数cij表示其与i之间边权。接下来一个数ti,若ai等于0,表示此点最多可容纳人数,若ai不等于0,则表示此点现有人数。
输出格式
  一个数,表示最少所需时间。
样例输入
4
2 2 5 3 3 2
1 4 2 3
0 2
0 3
样例输出
3
数据规模和约定
  10%的数据n<=5
  30%的数据n<=100
  另外10%的数据保证n个点形成一条链
  另外10%的数据ti={0,1},n<=20
  100%的数据1<=n<=10000,0<=cij,ti<=100000,本题均为随机数据(树深度较小)。