← 返回题目

题库练习保安站岗

← 上一题下一题 →

A6291 | $保安站岗$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

五一来临，某地下超市为了便于疏通和指挥密集的人员和车辆，以免造成超市内的混乱和拥挤，准备临时从外单位调用部分保安来维持交通秩序。 已知整个地下超市的所有通道呈一棵树的结构；某些通道之间可以互相望见。总经理要求所有通道的每个端点（也就是树的每个结点）都要有人全天候看守。在不同的通道端点安排保安所需的费用不同。 一个保安一旦站在某条通道的一个端点上，那么他除了能看守住他所站的那个端点外，也能看到这条通道的另一个端点。所以一个保安可能同时看守多个端点，因此没有必要在每个通道的端点都安排保安。 你的任务是：在保证所有结点都被看守到的前提下，使安排保安的总费用最小。

输入格式

第 1 行：一个整数 $n$，表示树中结点的数目。 接下来第 2 行至第 $n+1$ 行，每行描述一个结点的信息，格式为： > $i\ k\ m\ r_1\ r_2\ \dots\ r_m$ 含义为： - $i$：结点编号（$0 < i \le n$，编号不重复）； - $k$：在该结点安置一个保安所需的费用（$1 \le k \le 10000$）； - $m$：该结点的儿子个数； - 接下来 $m$ 个数 $r_1, r_2, \dots, r_m$：该结点的 $m$ 个儿子的编号。 整棵树有 $n$ 个结点，结点编号在 $1$ 到 $n$ 之间。

输出格式

输出一行一个整数，表示在能看守所有结点的前提下所需的最小总费用。

输入输出样例

输入 #1

6
1 30 3 2 3 4
2 16 2 5 6
3 5 0
4 4 0
5 11 0
6 5 0

输出 #1

C++ 编辑器

输入

输出