题意:

  P门课程,N个学生。给出每门课程的选课学生,求是否可以给每门课程选出一个课代表。课代表必须是选了该课的学生且每个学生只能当一门课程的。

题解:

  匈牙利算法的入门题。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = ;
int t;
int k, s;
int flag;
int p, n;
int vis[maxn];
int match[maxn];
vector<int> g[maxn];
void init() {
flag = ;
memset(match, -, sizeof(match));
for(int i = ; i <= p+n; i++) g[i].clear();
}
bool dfs(int u) {
vis[u] = ;
for(int i = ; i < g[u].size(); i++) {
int v = g[u][i], w = match[v];
if(w< || !vis[w]&&dfs(w)) {
match[u] = v;
match[v] = u;
return true;
}
}
return false;
}
int hungarian() {
int res = ;
for(int u = ; u <= s+p; u++) {
if(match[u] < ) {
memset(vis, , sizeof(vis));
if(dfs(u)) res++;
}
}
return res;
}
int main() {
scanf("%d", &t);
while(t--) {
init();
scanf("%d%d", &p, &n);
for(int i = ; i <= p; i++) {
scanf("%d", &k);
if(!k) flag = ;
while(k--) {
scanf("%d", &s);
g[i].push_back(s+p);
g[s+p].push_back(i);
}
}
if(flag || n<p) {
puts("NO");
continue;
}
int ans = hungarian();
if(ans == p) puts("YES");
else puts("NO");
}
}

最新文章

  1. 【原】使用Bmob作为iOS后台开发心得——查询关联关系(BmobRelation)
  2. 使用adjacent_difference要注意的小问题
  3. DTD中的属性类型
  4. User Settings in WPF
  5. Scrum 3.1 多鱼点餐系统开发进度(第三阶段项目构思与任务规划)
  6. Visual Studio Profiler 跟踪检查每个exe dll 性能 执行时间 CPU占用情况的方法
  7. POJ 2349 Arctic Network (最小生成树)
  8. Eclipse 调整代码颜色的地方
  9. 公布windows的&amp;quot;Universal Apps&amp;quot; Unity3D游戏
  10. Linux中git的使用
  11. Leetcode 804. Unique Morse Code Words 莫尔斯电码重复问题
  12. [Swift]LeetCode725. 分隔链表 | Split Linked List in Parts
  13. 第四节:MVC中AOP思想的体现(四种过滤器)并结合项目案例说明过滤器的实际用法
  14. Jarvis OJ A Piece Of Cake
  15. win平台下Path变量消失问题
  16. cocos2d-x 开发用到的工具
  17. MySQL配置文件以及服务的开启关闭重启
  18. android 巧用动画使您app风骚起来
  19. sublime text3 (Mac) 快捷键
  20. window 10 javac不是内部或外部命令

热门文章

  1. HDU2837 Calculation(扩展欧拉定理)
  2. flask实现基于elasticsearch的关键词搜索建议
  3. 事件监听和window.history以及自定义创建事件
  4. IBM Rational Software Architect V9.0安装图解
  5. 关于Mysql唯一索引的操作方法(添加删除)
  6. 【JavaScript】jQuery绑定事件
  7. 生产-消费模式的synchronized和lock实现(十)
  8. MySQL的备份
  9. BZOJ 1441: Min(裴蜀定理)
  10. 使用postMan测试insert或者update接口