Posted on 2010-08-21 14:43
acronix 阅读(127)
评论(0) 编辑 收藏 引用 所属分类:
hzshuai解题报告
题目就不说和分析了;
直接
cpp 代码:
#include <cstdio>
#include <memory.h>
bool g[110][310],flag,vis[310];
int match[310];
int p,n;
int SearchPath(int u)
{
for (int v = 1; v <= n; v ++)
if (g[u][v] && ! vis[v])
{
vis[v] = true;
if (match[v] == -1 || SearchPath(match[v]))
{
match[v] = u;
return 1;
}
}
return 0;
}
int main()
{
int i,j,k,t,v,cnt;
scanf("%d",&t);
while (t--)
{
scanf("%d %d", &p, &n);
for (i = 1; i <= p; i++)
for (j = 1; j <= n; j++)
g[i][j] = false;
for (i = 1; i <= n; i++)
match[i] = -1;
flag = true;
for (i = 1; i <= p; i++)
{
scanf("%d",&k);
if (k == 0)
flag = false;
while (k--)
{
scanf("%d",&v);
g[i][v] = true;
}
}
if (flag)
{
cnt = 0;
for (i = 1; i <= p; i++)
{
memset(vis,false,sizeof(vis));
cnt += SearchPath(i);
}
if (cnt == p)
printf("YES\n");
else printf("NO\n");
}
else printf("NO\n");
}
return 0;
}