Headmaster's Headache

he headmaster of Spring Field School is considering employing some new teachers for certain subjects. There are a number of teachers applying for the posts. Each teacher is able to teach one or more subjects. The headmaster wants to select applicants so that each subject is taught by at least two teachers, and the overall cost is minimized.

Input

The input consists of several test cases. The format of each of them is explained below:

The first line contains three positive integers S, M and N. S (≤ 8) is the number of subjects, M (≤ 20) is the number of serving teachers, and N (≤ 100) is the number of applicants.

Each of the following M lines describes a serving teacher. It first gives the cost of employing him/her (10000 ≤ C≤ 50000), followed by a list of subjects that he/she can teach. The subjects are numbered from 1 to S. You must keep on employing all of them. After that there are N lines, giving the details of the applicants in the same format.

Input is terminated by a null case where S = 0. This case should not be processed.

Output

For each test case, give the minimum cost to employ the teachers under the constraints.

Sample Input

2 2 210000 120000 230000 1 240000 1 20 0 0

Sample Output

60000 题目大意：某校有n个教师和m个求职者。已知每人的工资和能交的课程集合，要求支付最少的工资使得每门课都至少有两名教师教学。在职教师必须招聘 输入格式：每组数据的第一行为3个整数s、m和n（1<=s<=8,1<=m<=20,1<=n<=100），即科目的个数、在职教师个数和申请者个数：以下m行每行用一些整数描述一位在职教师，其中第一个整数c（1000<=c<=50000）是工资，接下来的若干整数是他能教的科目列表（课程编号为1~s之间的整数）；接下来的n行描述申请者，格式同上。输入结束标志为s=0. 输出格式：对于每组数据，输出工资总额的最小值。 分析： 　　每一个老师可以教多门课程，而且在职教师必须招聘，那么在职教师能教的课就应该全部教，假设他们教的课程达到状态st。那么答案就是 　　　　　　　　　　所有在职教师的工资+（完成最终状态-st状态）的所有求职工的工资 　　科目个数最多为8，用16位2进制数来表示。2进制中从右往左数，前8为表示有1位老师教该门课程，后8为表示有2位老师教（该位-8）的课程，当s=8时，00000010 00000001表示1个老师教第一门课，2个老师教第2门课。这样 11111111 00000000 即为所要求的目标状态，代码中用T表示。 　　令dp[i][j]表示在前 j 个求职工中达到状态 i的最小花费。用st表示当前状态，则 　　　　　　dp[i][j] = min{dp[i][j], dp[i][j+1], dp[i+第j个人能够教的科目][j+1] +第j个人的工资} 　　定义函数int DP(int st,int i)表示第ｉ个人开始到ｎ个人结束，从状态 st 开始到目标状态的最小花费。这里用到记忆化搜索。

　　题目中没有给出每个老师会教的课程的数目，而是直接给课程的编号，所以要用gets输入，用sscanf提取其中的数字，这里我用动态二维数组保存每个求职者能教的课程。 　　　　sscanf(*s,"%d",&y)表示从字符串s中取出第一个数字，并且保存在y中 　　　　isdigit()判断字符c是否是数字，当字符c我0-9时返回非0值，否则返回0。 　　　for(j=0;j

　　　　　　sscanf(t+j,"%d",&y); 　　　　　　for(;isdigit(t[j]);j++); 　　　　　　j++; 　　}

　比如对于一字符串t[]=“1 2 3 4”，先取出数字1，之后j是数字跳过，再往后从t+2开始，取出数字2... 　　

代码如下：

1 # include
     
       2 # include
      
        3 # include
       
         4 # include
        
          5 # include
         
              //isdigit()函数包含在ctype.h头文件中 6 # define INF 0x3f3f3f3f     7 # define N (1<<16)+5 8 using namespace std; 9 10 int min(int a,int b){11     return a
          
         
        
       
      
     

 

好辛苦啊，为了看懂用了3个小时。。。不过还有疑问，为什么INF要在0x3f3f3f3f这个范围左右，改成其他的就不对了