关于本题二分图的匹配
关系始终是加单向边
用左边去匹配右边,match表示的是右边的人匹配的对应的左边的点

/*
关于本题二分图的匹配
链接的关系始终是单向边
用左边去匹配右边,match表示的是右边的人匹配的对应的左边的点
*/ #include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define maxn 505
int mp[maxn][maxn],match[maxn];
bool vis[maxn];
int p,n; bool dfs(int x){//第x门课是否有人匹配
for(int i=;i<=n;i++){
if(!vis[i] && mp[x][i]){//枚举每门课可以选择的人
vis[i]=;
//第i个人已经匹配了match[i]课
if(match[i]==-||dfs(match[i])){
match[i]=x;return ;
}
}
}
return ;
}
int sum(){
int res=;
for(int i=;i<=p;i++){//每门课是否有学生来匹配
memset(vis,,sizeof vis);
if(dfs(i))res++;
}
return res;
}
void init(){
memset(match,-,sizeof match);
memset(mp,,sizeof mp);
}
int main(){
int t;cin>>t;
while(t--){
init();
cin>>p>>n;//p门课,n个学生
for(int i=;i<=p;i++){//喜欢第i门课的学生有k个
int k,j;scanf("%d",&k);
while(k--){
scanf("%d",&j);
mp[i][j]=;
}
}
int ans=sum();
if(ans==p)puts("YES");
else puts("NO");
}
}

最新文章

  1. jQuery链式操作[转]
  2. CentOs下jdk的安装
  3. POJ 2155 Matrix(二维树状数组+区间更新单点求和)
  4. BZOJ3170: [Tjoi 2013]松鼠聚会
  5. Android应用性能优化之使用SQLiteStatement优化SQLite操作
  6. 无责任Windows Azure SDK .NET开发入门篇三[使用Azure AD 管理用户信息--3.3 Details用户详细信息]
  7. qt creator中使用qwt插件
  8. Shell until循环
  9. fs.rename可以重新写入文件
  10. uml系列(三)——用例图
  11. C#表达式和语句
  12. 解题(DirGraCheckPath--有向图的遍历(深度搜索))
  13. lsb隐写
  14. redis ERR This instance has cluster support disabled
  15. Python编程-数据库-利用PyMysql访问windows下的MySql数据库
  16. (素材源代码) 猫猫学iOS 之UIDynamic重力、弹性碰撞吸附等现象牛逼Demo
  17. sencha touch 可自动增长高度TextArea
  18. Codeforces 374 C. Travelling Salesman and Special Numbers (dfs、记忆化搜索)
  19. C++构造函数后面的冒号
  20. PHP双向队列,双端队列代码

热门文章

  1. IPv6 三个访问本地地址的小Tips
  2. [kuangbin带你飞]专题一 简单搜索 - K - 迷宫问题
  3. Ctrl快捷键
  4. php 获取不到post的值
  5. 以 Ubuntu 为例:清理 linux 系统的&quot;垃圾&quot;文件
  6. eclipse导出说明文档
  7. [转]Nginx配置详解
  8. redis笔记_源码_字典dict
  9. Emacs基本操作说明
  10. oracle 删除掉重复数据只保留一条