P5194: 有线电视网-训练套题T13T4
传统题
2.000s
时间限制
512MB
内存限制
6 提交
6 解决
【题目描述】
有线电视网（tele.pas/c/cpp）
[问题描述]
某收费有线电视网计划转播一场重要的足球。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的赛场，树叶为各个用户终端。其他中转站为该树的内部结点。
从转播站到转播站以及从转播站到用户的信号输出费用都是已知的，一场转播的总费用等于传输信号费用总和。
现在每个用户都准备了一笔费用想观看精彩的足球赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。
写一个程序找出一个方案使得有线电视网不亏本的情况下使观看转播的用户尽可能多。
[输入格式]
第一行为N(N <= 3000)和M(M < N)，N为电视网的结点总数，M表示用户终端数量。
第一个转播站（根结点）编号为1，其他的转播站编号为2到N-M，用户终端编号为N-M+1到N。
接下来N-M行每行表示转播站的数据，格式如下：
K, A1, C1, A2, C2... AK, CK
K表示该转播站下接K个结点（转播站或用户），每个结点对应一对整数A与C，A表示结点编号，C表示从当前转播站传输信号到结点A的费用。
最后一行依次表示所有用户为观看比赛准备支付的费用。
[输出格式]
一行，代表上述问题所要求的最大用户数。
[样例输入]
5 3
2 2
2 5 3
2 3
2 4 3
3 4
2
[样例输出]
2