洛谷—— P2417 课程
2024-10-20 20:47:44
https://www.luogu.org/problemnew/show/2417
题目描述
n个学生去p个课堂,每一个学生都有自己的课堂,并且每个学生只能去一个课堂,题目要求能够安排每一个课堂都有人吗?
输入输出格式
输入格式:
第一行是测试数据的个数,
每组测试数据的开始分别是p和n,
接着p行,每行的开始是这个课堂的学生人数m,接着m个数代表该课堂的学生编号
输出格式:
如果该组数据能够这样安排就输出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){;}
最新文章
- .NET平台开源项目速览(15)文档数据库RavenDB-介绍与初体验
- Ubuntu下安装MySQL-python教程
- Bad Request - Request Too Long
- Spring-cloud &; Netflix 源码解析:Eureka 服务注册发现接口 ****
- MFC 关于如何实现浏览文件
- angularjs的$filter使用
- 在Azure上搭建Orchard CRM入口网站
- CSS 实现加载动画之七-彩环旋转
- 跟着上一个tcpServer 一起来的
- sqlldr使用
- jquery 实现复选框单选
- 解决mysql不能远程登录的问题
- poj 3641 Pseudoprime numbers(快速幂)
- 访问Access日期字段
- Java建造者模式
- 20175314 《Java程序设计》第八周学习总结
- JS-jquery对象和dom对象的属性操作区别
- ERROR 2002 (HY000): Can&#39;t connect to local MySQL server through socket &#39;/var/run/mysqld/mysqld.sock&#39; (2)
- Java 浅拷贝,深拷贝
- BZOJ2434[Noi2011]阿狸的打字机——AC自动机+dfs序+树状数组
热门文章
- mybatis是如何防止sql注入?
- ogre3D学习基础16 -- 手动创建实体(ManualObject)
- Leetcode 558.四叉树交集
- 动态规划--找零钱 coin change
- 微信公众平台OAuth2.0网页授权
- 设计模式(一)单例模式:2-懒汉模式(Lazy)
- POJ 2763 Housewife Wind(DFS序+LCA+树状数组)
- POJ 3648 Wedding(2-SAT的模型运用+DFS | Tarjan)
- hihoCoder 第136周 优化延迟(二分答案+手写堆)
- BZOJ 1067 降雨量(RMQ-ST+有毒的分类讨论)