P10181: 解题

---

【题目描述】

【问题描述】 
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
【数据规模】
对于40%的数据,3<=m,n<=10,
对于100%的数据,3<=m,n<=60,1<=li<=6

【提示】

搜索是基础算法.虽然近几年中NOIP搜索题占的比率并不大,但是在考试临近结束时,或者有题不会时,写一个简单的搜索程序往往会带来意想不到的结果.比如去年的金明的预算方案,有很多大牛虽然写了DP但是某一个小细节处理错了,0分;那些写搜索的反而至少能得40-50分,加几条剪枝甚至能达到80-90分.可见搜索在实战中的作用.

 

这道题并不难,只需加几条剪枝就可全过:

 

1 可行性剪枝,如果当前选择的高手的数量已经大于等于当前最优解的数量,剪.这也是最基础,最简单,但却是最实用的剪枝之一.

2 重复数据 数据中不可避免地会出现某一个高手会做的题目,有另外一个高手全会做的情况.这种情况下,这个高手就不需要了,因为它完全可以被另外那个高手取代.

3 仅有情况 有的题只能被一位高手解决,所以在搜索之前把这位高手会做的题目删去吧,最优解中一定包含这位高手,所以这些题一定能被解决.

题目类型~

搜索专题 

咻咻~

提交答案 状态 返回