1375: 解题
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Normal Judger
Creator：
Submit：18
Solved：1
Description
【问题描述】
小智被布置了m道作业题,可是他一道也不会..但他知道有n位高手,并知道每位高手会做哪些题,请问小智至少要请多少位高手,才能把所有的题都做出来?
【输入】
第一行两个整数m,n表示有m道作业题和n位高手,作业题以1..m编号.接下来n行,第i+1行第一个数li表示第i位高手会做的题目的数量,接下来li个数表示第i位高手会做哪些题目.
【输出】
一个数,小智至少要请多少位高手?
【输入样例】
4 4
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
Input
第一行两个整数m,n表示有m道作业题和n位高手,作业题以1..m编号.接下来n行,第i+1行第一个数li表示第i位高手会做的题目的数量,接下来li个数表示第i位高手会做哪些题目.
Output
一个数,小智至少要请多少位高手?
Sample Input Copy
4 4
2 1 2
1 4
3 2 3 4
2 1 3 Sample Output Copy
2HINT
搜索是基础算法.虽然近几年中NOIP搜索题占的比率并不大,但是在考试临近结束时,或者有题不会时,写一个简单的搜索程序往往会带来意想不到的结果.比如去年的金明的预算方案,有很多大牛虽然写了DP但是某一个小细节处理错了,0分;那些写搜索的反而至少能得40-50分,加几条剪枝甚至能达到80-90分.可见搜索在实战中的作用.
这道题并不难,只需加几条剪枝就可全过:
1 可行性剪枝,如果当前选择的高手的数量已经大于等于当前最优解的数量,剪.这也是最基础,最简单,但却是最实用的剪枝之一.
2 重复数据 数据中不可避免地会出现某一个高手会做的题目,有另外一个高手全会做的情况.这种情况下,这个高手就不需要了,因为它完全可以被另外那个高手取代.
3 仅有情况 有的题只能被一位高手解决,所以在搜索之前把这位高手会做的题目删去吧,最优解中一定包含这位高手,所以这些题一定能被解决.