TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1687
  • 题目
  • P1687赛事直播
    限制 : 时间限制 : - MS   空间限制 : 128000 KB
    评测说明 : 时限1000ms
    问题描述

      一个网络直播平台计划直播欧洲杯足球赛。网络中的中转点和观看点构成了一个树形结构。这棵树的根是直播点,它将直播比赛。其中观看点是树的叶节点,他们是可能要观看比赛的用户(用户可以选择不看比赛,这样就不用缴观看费)。其他非根节点、非叶节点的中间节点就是直播数据的中间转发点,即中转点。
       将比赛数据从树中一个点传到另一个点需要一定的花费。整个直播的费用就是所有传输费用的总和。
        每一个用户都给出了自己愿意支付的观看费用。直播公司要决定是否给这个用户提供直播服务。例如:给一个用户(叶节点)直播比赛的花费很大,而这个用户愿意支付的费用却很少时,直播公司可以选择不给他直播。
       找到一个方案使得观看欧洲杯直播的客户尽可能多,且直播公司不能亏本(直播的费用不超过所有观看比赛的客户的缴费总和)。

    输入格式

    第一行包含两个整数N和P。
    N表示表示树的节点数,P表示想要看比赛的用户数(叶节点数)。
    树的根为1号节点,中转节点的编号为2到N-P,用户的节点编号为N-P+1到N。

    接下来的N-P行每行表示一个非客户点的情况,其中第i行表示编号i-1的点的信息
    每行描述如下:
    T A1 C1 A2 C2 …… At Ct
    表示对应点能将信号传给T个点,每一个包含两个数A和C,A表示中转点或用户点的编号,C表示传输的花费。

    最后一行有P个整数分别表示N-P+1到N号用户愿意支付的费用。

    输出格式

    一个整数,在不亏本的前提下,可能的最大的用户数

    样例输入

    样例输入1
    5 3
    2 2 2 5 3   
    2 3 2 4 3  
    3 4 2        
    样例输入2
    5 3
    2 2 2 5 3
    2 3 2 4 3
    4 4 2
    样例输入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

    样例输出

    样例输出1
    2
    样例输出2
    3
    样例输出3
    5

    提示

    对于40%的数据:2<=N<=300,1<= P<=N-1
    对于100%的数据:2<=N<=3000,1<=P<=N-1  每次传输的费用和每个用户愿意支付的费用都<=100