← 返回题单
题单练习 树上问题
← 上一题 下一题 →

A6286 | 有线电视网

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。

从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。

现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。

写一个程序找出一个方案，使得有线电视网在不亏本的情况下，使观看转播的用户数尽可能多。

输入格式

第一行包含两个用空格隔开的整数 $N$ 和 $M$：

  • $N$ 为整个有线电视网的结点总数；
  • $M$ 为用户终端的数量。

    • 其中 $2 \le N \le 3000$，$1 \le M \le N - 1$。

    结点按如下方式编号：
  • 根结点（现场直播站）编号为 $1$；
  • 其他转播站编号为 $2$ 到 $N - M$；
  • 用户终端编号为 $N - M + 1$ 到 $N$。

    • 接下来有 $N - M$ 行，第 $i+1$ 行表示第 $i$ 个转播站的数据，格式为：

    $K\ A_1\ C_1\ A_2\ C_2\ \dots\ A_K\ C_K$

    含义为：
  • 该转播站下接有 $K$ 个结点（可以是转播站或用户终端）；
  • 对于每个这样的结点，给出一对整数 $(A_j, C_j)$：
- $A_j$ 为下挂结点的编号；
- $C_j$ 为从当前转播站传输信号到结点 $A_j$ 的费用。

最后一行包含 $M$ 个整数，依次表示各个用户终端愿意支付的费用。
第一个数对应结点 $N-M+1$，第二个数对应结点 $N-M+2$，以此类推。

单次传输成本和用户愿意交的费用均不超过 $10$。

输出格式

输出仅一行，包含一个整数，表示在不亏本的前提下，最多可以让多少个用户观看比赛。

输入输出样例

输入 #1
5 3
2 2 2 5 3
2 3 2 4 3
3 4 2
输出 #1
2
C++ 编辑器
输入
输出