问题 5262 --比赛转播--树型动态规划训练T6

5262: 比赛转播--树型动态规划训练T6

时间限制: 1 Sec  内存限制: 128 MB
提交: 7  解决: 6
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][168kb]

题目描述

比赛转播(tele.pas/c/cpp)

一个电视网络计划转播一场重要的足球比赛。网络中的传输点和接收点(即用户)可以 表示一棵树。这棵树的根是一个传输点,它将转播比赛。树的叶节点是可能要接受这场比赛 的用户(他当然可以选择不看比赛,这样就不要交款)。其他非根节点,非叶节点的中间节点 为数据的中转站。

将一个信号从一个传输点传到另一个传输点的花费是给定的。整个转播的费用就是每一 个传输费用的总和。  每一个用户(叶节点)都准备付一定的钱来看这场比赛。电视网络公司 要决定是否要给这个用户提供电视信号。例如:给一个节点传输信息的花费太大,而他愿意 的付款也很少时,网络公司可能选择不给他转播比赛。

写一个程序,找到一个传输方案使最多的用户能看到转播比赛,且转播的费用不超过所 有接收信号用户的交款。

程序名:tele

输入格式:

输入文件的第一行包含两个整数 N 和 M(2<=N<=3000,1<=M<=N-1)。N,M 表示分别表 示树的节点数和想观看比赛的用户数。树的根节点用 1 表示,中间节点的标号为 2~N-M,用 户的节点标号为 N-M+1~N。

接下来的 N-M 行表示传输点的信息(依次是节点 1,2……):

K A1 C1 A2 C2 …… Ak Ck

表示一个传输点将信号传给 K 个用户,每一个包含两个数 A 和 C,A 表示传输点或用户 的节点号,C 表示传输的花费。

最后一行含有用户的数据,有 M 个整数表示他们看这场比赛愿意的付费。 输出格式:

仅一行包含一个整数,最大的用户数。 输入样例 1

5 3

2 2 2 5 3

2 3 2 4 3

3 4 2

输出样例 1

2

输入样例 2

5 3

2 2 2 5 3

2 3 2 4 3

4 4 2

输出样例 2

3

输入样例 3

9 6

 

 

 

 

3 2 2

3

2

9

3

2 4 2

5

2

 

 

3 6 2

7

2

8

2

4 3 3

3

1

1

 


输出样例 3

5

输入

输出

提示

来源

[提交][状态]