题目大意:

一共有N个学生跟P门课程,一个学生可以任意选一 门或多门课,问是否达成: 
  1.每个学生选的都是不同的课(即不能有两个学生选同一门课)
  2.每门课都有一个代表(即P门课都被成功选过)
输入为:
第一行一个T代表T组数据
P N(P课程数, N学生数)
接着P行:
第几行代表第几门课程,首先是一个数字k代表对这门课程感兴趣的同学的个数,接下来是k个对这门课程感兴趣同学的编号。
输出为:
若能满足上面两个要求这输出”YES”,否则为”NO”
注意:是课程匹配的学生,学生没课上没事.....

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define maxn 505
bool G[maxn][maxn];///图存储
bool vis[maxn];///标记点是否被遍历过
int P[maxn];///表示第i个学生选的是第P[i]门课程
int n, m;///n门课程 m个学生 bool Find(int u)
{
for(int i=; i<=m; i++)
{
if(G[u][i] && !vis[i])///判断第i个学生是否喜欢第U门课, 并且判断第i个学生是否被遍历过
{
vis[i] = true;///标记第i个学生被遍历过了
if( !P[i] || Find(P[i]) )/**判断第i个学生是否选过课了,如果选过了就看看能否更改这个学生所选的课程,让这个学生选u这门课*/
{///如果u这门课 i是可以选的,退出函数完成筛选,否则继续为u进行挑选学生,直到没有
P[i] = u;
return true;
}
}
}
return false;
} int main()
{
int T, v, j, i, k;
scanf("%d", &T); while(T--)
{
memset(G, false, sizeof(G));
memset(P, , sizeof(P));
scanf("%d %d",&n, &m); for(i=; i<=n; i++)
{
scanf("%d", &k);
while(k --)
{
scanf("%d", &v);
G[i][v] = true;
} } for(j=; j<=n; j++)
{/**我们每一次进行搜索的时候所有的点都要置为未遍历,因为我们每一次选课都要重新分配课程*/
memset(vis, false, sizeof(vis));
/**判断 j 课程是否找到了自己的学生**/
if( !Find(j) )
break;
} if( j == n + )
puts("YES");
else
puts("NO");
}
return ;
}

最新文章

  1. shell下&gt;和&gt;&gt;的区别
  2. Windows 无法自动将 IP 协议堆栈绑定到网络适配器。解
  3. Delphi XE5 for android 使用 BITMAP STYLE DESIGNER 改变控件背景
  4. MVC5 - ASP.NET Identity登录原理 - Claims-based认证和OWIN -摘自网络
  5. sublime php语法检查
  6. select组件2
  7. ORACLE数字转换人民币大写
  8. 关于Staruml与powerdesigner启动使用中的问题
  9. 2014年百度之星程序设计大赛 - 资格赛 第三题 Xor Sum
  10. webstrom 快捷键(Idea可用)
  11. leetcode day5
  12. JS中的函数、BOM和DOM操作
  13. 【Docker】(6)---Dockerfile文件
  14. 关于mysql安装后在客户端cmd插入语句无法执行的问题
  15. domReady
  16. net4log 日志管理
  17. linux系统下各类软件安装笔记
  18. WebStrom配置node.js
  19. HDU - 5818 Joint Stacks 比较大の模拟,stack,erase
  20. BroadcastReceiver接收电量变化的广播-------在代码中动态创建接受者

热门文章

  1. Array数组基本案例:图书基本录入输出系统
  2. 学习《Spring 3.x 企业应用开发实战》Day-1
  3. .net之页面生面周期
  4. 转载:C# 之泛型详解
  5. C#中的转义字符
  6. __name__属性
  7. 基于CANVAS与MD5的客户端生成验证码
  8. js原生封装自定义滚动条
  9. myeclipse跟eclipse中使用github做版本控制工具
  10. protocol buffer使用简介