https://www.luogu.org/problemnew/show/2417

题目描述

n个学生去p个课堂,每一个学生都有自己的课堂,并且每个学生只能去一个课堂,题目要求能够安排每一个课堂都有人吗?

输入输出格式

输入格式:

第一行是测试数据的个数,

每组测试数据的开始分别是p和n,

接着p行,每行的开始是这个课堂的学生人数m,接着m个数代表该课堂的学生编号

输出格式:

如果该组数据能够这样安排就输出YES,否则输出NO。

输入输出样例

输入样例#1: 复制

2
3 3
3 1 2 3
2 1 2
1 1
3 3
2 1 3
2 1 3
1 1
输出样例#1: 复制

YES
NO

说明

对于100%的数据,n\le 100,m\le 20000n≤100,m≤20000

 #include <cstring>
#include <cstdio> inline void read(int &x)
{
x=; register char ch=getchar();
for(; ch>''||ch<''; ) ch=getchar();
for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';
} const int M();
const int N(); int n,p,sumvis;
bool link[N][M];
int vis[M],mat[M]; bool find(int u)
{
for(int v=; v<=n; ++v)
if(vis[v]!=sumvis&&link[u][v])
{
vis[v]=sumvis;
if(!mat[v]||find(mat[v]))
{
mat[v]=u;
return ;
}
}
return false;
} inline bool work()
{
int m,cnt=;
read(p),read(n);
for(int u=; u<=p; ++u)
{
read(m);
for(int v; m--; )
read(v),link[u][v]=;
}
for(int i=; i<=p; ++i)
{
sumvis++;
cnt+=find(i);
}
return cnt==p;
} inline void init()
{
sumvis=;
memset(mat,,sizeof(mat));
memset(vis,,sizeof(vis));
memset(link,,sizeof(link));
} int Presist()
{
int t; read(t);
for(; t--; init())
if(!work()) puts("NO");
else puts("YES");
return ;
} int Aptal=Presist();
int main(int argc,char**argv){;}

最新文章

  1. .NET平台开源项目速览(15)文档数据库RavenDB-介绍与初体验
  2. Ubuntu下安装MySQL-python教程
  3. Bad Request - Request Too Long
  4. Spring-cloud &amp; Netflix 源码解析:Eureka 服务注册发现接口 ****
  5. MFC 关于如何实现浏览文件
  6. angularjs的$filter使用
  7. 在Azure上搭建Orchard CRM入口网站
  8. CSS 实现加载动画之七-彩环旋转
  9. 跟着上一个tcpServer 一起来的
  10. sqlldr使用
  11. jquery 实现复选框单选
  12. 解决mysql不能远程登录的问题
  13. poj 3641 Pseudoprime numbers(快速幂)
  14. 访问Access日期字段
  15. Java建造者模式
  16. 20175314 《Java程序设计》第八周学习总结
  17. JS-jquery对象和dom对象的属性操作区别
  18. ERROR 2002 (HY000): Can&#39;t connect to local MySQL server through socket &#39;/var/run/mysqld/mysqld.sock&#39; (2)
  19. Java 浅拷贝,深拷贝
  20. BZOJ2434[Noi2011]阿狸的打字机——AC自动机+dfs序+树状数组

热门文章

  1. mybatis是如何防止sql注入?
  2. ogre3D学习基础16 -- 手动创建实体(ManualObject)
  3. Leetcode 558.四叉树交集
  4. 动态规划--找零钱 coin change
  5. 微信公众平台OAuth2.0网页授权
  6. 设计模式(一)单例模式:2-懒汉模式(Lazy)
  7. POJ 2763 Housewife Wind(DFS序+LCA+树状数组)
  8. POJ 3648 Wedding(2-SAT的模型运用+DFS | Tarjan)
  9. hihoCoder 第136周 优化延迟(二分答案+手写堆)
  10. BZOJ 1067 降雨量(RMQ-ST+有毒的分类讨论)