网络巡视

Grade 100 Open Time Wednesday, 17 June 2020, 5:30 PM
Discount 0.8 Time Discount Wednesday, 17 June 2020, 5:30 PM
Allow late Yes Close Time Wednesday, 17 June 2020, 5:30 PM
Input file net.in Output file net.out

【题目描述】网络巡视(net)BSOJ 1116

通信公司的网络各结点构成了一棵树,为了防止破坏,需要在一些结点安置巡视岗,安置巡视岗的结点可以看到相邻结点的情况。但不同的结点安置巡视岗的花费代价不同,问如何在保证全部结点安全的情况下花费的代价最小。

【输入格式】

输入数据表示一棵树,描述如下:

第1行一个整数n,表示树中结点的数目。

第2行至第n+1行,每行描述每个结点信息,依次为:该结点标号i(0<i≤n),在该结点安置巡视岗所需的经费k,该结点的儿子数m,接下来m个数,分别是这个结点的m个儿子的标号r1,r2,…,rm

对于一个n个结点的树,结点标号在1到n之间,且标号不重复。

【输出格式】

输出仅包含一个数,为所求的最少的代价数。

【输入样例】

6

1 30 3 2 3 4

2 16 2 5 6

3 5 0

4 4 0

5 11 0

6 5 0

【输出样例】

25

【样例说明】

样例如图4.61所示,巡视岗设置结点为2,3,4。