题目描述

给定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 样例输入 5 2 1 2 2 2 3 2 3 4 2 4 5 2 5 1 1 -1 1 -1 1 样例输出 0 样例输入 5 2 1 2 2 2 3 2 3 4 2 4 5 2 5 1 -1 1 -1 1 -1 样例输出 -1

输入格式

第一行一个正整数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 样例输入 5 2 1 2 2 2 3 2 3 4 2 4 5 2 5 1 1 -1 1 -1 1 样例输出 0 样例输入 5 2 1 2 2 2 3 2 3 4 2 4 5 2 5 1 -1 1 -1 1 -1 样例输出 -1

输出格式

仅一个整数, 为代价最小的选择方案的代价. 样例输入 3 1 1 2 2 3 1 3 10 20 -3 样例输出 -3 样例输入 5 2 1 2 2 2 3 2 3 4 2 4 5 2 5 1 1 -1 1 -1 1 样例输出 0 样例输入 5 2 1 2 2 2 3 2 3 4 2 4 5 2 5 1 -1 1 -1 1 -1 样例输出 -1

3
1 1
2 2 3
1 3
10 20 -3
样例输出
-3
样例输入
5
2 1 2
2 2 3
2 3 4
2 4 5
2 5 1
1 -1 1 -1 1
样例输出
0
样例输入
5
2 1 2
2 2 3
2 3 4
2 4 5
2 5 1
-1 1 -1 1 -1
样例输出
-1

-3
样例输入
5
2 1 2
2 2 3
2 3 4
2 4 5
2 5 1
1 -1 1 -1 1
样例输出
0
样例输入
5
2 1 2
2 2 3
2 3 4
2 4 5
2 5 1
-1 1 -1 1 -1
样例输出
-1

来源

蓝桥杯 算法训练