Dotcpp  >  编程题库  >  蓝桥杯算法训练VIP-Buying Sets
题目 1587:

蓝桥杯算法训练VIP-Buying Sets

时间限制: 2s 内存限制: 192MB 提交: 163 解决: 80

题目描述

给定n个集合,  要求选出其中某些集合,  使得这些集合的并集的势,  等于选出的集合的数目.

对于任意的k(1< =k< =n),  满从中选出任意k个集合,  这k个集合的并集的势一定大于等于k.

每个集合有一个权值,  每个选择方案的代价是所选的集合的权值的和.

请输出代价最小的选择方案的代价.

当然,  不选择任何一个集合是一个可行的方案(权值和为0),  但不一定最优(权值和可以为负).

输入格式

第一行一个正整数n(1< =n< =300),  为集合个数. 

在接下来n行中,  第i行描述第i个集合: 

首先给出一个正整数m[i]为该集合的势,  显然1< =m[i]< =n. 

接下来m[i]个在1到n之间的整数,  表示该集合中的元素. 

最后一行n个整数,  为每个集合的权值,  绝对值不超过1e6. 

输出格式

仅一个整数,  为代价最小的选择方案的代价. 

样例输入

3
1 1
2 2 3
1 3
10 20 -3

样例输出

-3

提示

零基础同学可以先学习视频课程,包含C/C++、Python、百练、蓝桥杯辅导、算法数据结构等课程,提供视频讲解以及配套习题,还有老师答疑,点击这里了解课程详情
标签