Description
n个学生去p个课堂，每一个学生都有自己的课堂，并且每个学生只能去一个课堂，题目要求能够安排每一个课堂都有人吗？
Input
第一行是测试数据的个数，
每组测试数据的开始分别是p和n，
接着p行，每行的开始是这个课堂的学生人数m，接着m个数代表该课堂的学生编号
Output
如果该组数据能够这样安排就输出YES，否则输出NO。
很明显的一个二分图匹配裸题,注意判断(p >n)时候,显然不能满足每一个课堂都有人,这个条件要在输入结束之后判断.
二分图匹配就不多BB了 qwq
代码
#include<cstdio>
#include<cctype>
#include<cstring>
#define clear(a) memset(a,0,sizeof a)
#define R register
using namespace std;
inline void in(int &x)
{
int f=1;x=0;char s=getchar();
while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}
while(isdigit(s)){x=x*10+s-'0';s=getchar();}
x*=f;
}
int T,n,p,match[20008];
int head[20008],tot,ans;
struct cod{int u,v;}edge[20008*4];
inline void add(int x,int y)
{
edge[++tot].u=head[x];
edge[tot].v=y;
head[x]=tot;
}
bool vis[20008];
bool find(int x)
{
for(R int i=head[x];i;i=edge[i].u)
{
if(!vis[edge[i].v])
{
vis[edge[i].v]=1;
if(!match[edge[i].v] or find(match[edge[i].v]))
{
match[edge[i].v]=x;
return true;
}
}
}
return false;
}
int main()
{
in(T);
while(T--)
{
in(p),in(n);ans=tot=0;
clear(head);clear(match);clear(edge);clear(vis);
for(R int i=1,x,y;i<=p;i++)
{
in(x);
while(x--)
{
in(y);
add(i,y);
}
}
if(p>n){puts("NO");continue;}
for(R int i=1;i<=p;i++)
{
clear(vis);
if(find(i))ans++;
}
puts(ans==p?"YES":"NO");
}
}