4801: 解题
内存限制：128 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：2
通过：2
题目描述
【问题描述】
XX被布置了m道作业题,可是他一道也不会..但他知道有n位高手,并知道每位高手会做哪些题,请问XX至少请多少位高手,才能把所有的题都做出来?
【输入】
第一行两个整数m,n表示有m道作业题和n位高手,作业题以1..m编号.接下来n行,第i+1行第一个数li表示第i位高手会做的题目的数量,接下来li个数表示第i位高手会做哪些题目.
【输出】
一个数,XX至少要请多少位高手?
输入格式
4 4
2 1 2
1 4
3 2 3 4
2 1 3
2 1 2
1 4
3 2 3 4
2 1 3
输出格式
2
数据范围与提示
对于40%的数据,3<=m,n<=10,
对于100%的数据,3<=m,n<=60,1<=li<=6
1 可行性剪枝,如果当前选择的高手的数量已经大于等于当前最优解的数量,剪.这也是最基础,最简单,但却是最实用的剪枝之一.
2 重复数据 数据中不可避免地会出现某一个高手会做的题目,有另外一个高手全会做的情况.这种情况下,这个高手就不需要了,因为它完全可以被另外那个高手取代.
3 仅有情况 有的题只能被一位高手解决,所以在搜索之前把这位高手会做的题目删去吧,最优解中一定包含这位高手,所以这些题一定能被解决.