记录编号	8442	评测结果	AAAAAAAAAA
题目名称	[USACO Open05] 疾病管理	最终得分	100
用户昵称	BYVoid	是否通过	通过
代码语言	C++	运行时间	0.139 s
提交时间	2008-11-14 12:03:52	内存使用	0.32 MiB

#include <iostream>

using namespace std;

const int MAXD=16;
const int MAXN=1001;

int D[MAXN][MAXD];
int sel[MAXD];
int N,Dcnt,K,Ans=0;

void init()
{
	int i,j;
	freopen("disease.in","r",stdin);
	freopen("disease.out","w",stdout);
	scanf("%d%d%d",&N,&Dcnt,&K);
	for (i=1;i<=N;i++)
	{
		scanf("%d",&D[i][0]);
		for (j=1;j<=D[i][0];j++)
		{
			scanf("%d",&D[i][j]);
		}
	}
}

void DFS(int p,int c) //第p疾病
{
	if (c==K+1)
	{
		int i,j,cnt=0;
		bool invalid;
		for (i=1;i<=N;i++)
		{
			invalid=false;
			for (j=1;j<=D[i][0];j++)
			{
				if (!sel[D[i][j]])
				{
					invalid=true;
					break;
				}
			}
			if (!invalid)
			{
				cnt++;
			}
		}
		if (cnt > Ans)
			Ans=cnt;
		return;
	}
	if (p>Dcnt)
		return;
	sel[p]=true;
	DFS(p+1,c+1);
	sel[p]=false;
	if (p+1<=Dcnt)
		DFS(p+1,c);
}

int main()
{
	init();
	DFS(1,1);
	cout << Ans;
	return 0;
}