问题 5552 --【搜索基础】解题

5552: 【搜索基础】解题

时间限制: 1 Sec  内存限制: 128 MB
提交: 54  解决: 13
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][84kb]

题目描述

解题solve.pas/c/cpp

【问题描述】 
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 仅有情况 有的题只能被一位高手解决,所以在搜索之前把这位高手会做的题目删去吧,最优解中一定包含这位高手,所以这些题一定能被解决.

来源

[提交][状态]