POJ - 1469 COURSES (匈牙利算法入门题)
2024-09-04 10:40:43
题意:
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");
}
}
最新文章
- 【原】使用Bmob作为iOS后台开发心得——查询关联关系(BmobRelation)
- 使用adjacent_difference要注意的小问题
- DTD中的属性类型
- User Settings in WPF
- Scrum 3.1 多鱼点餐系统开发进度(第三阶段项目构思与任务规划)
- Visual Studio Profiler 跟踪检查每个exe dll 性能 执行时间 CPU占用情况的方法
- POJ 2349 Arctic Network (最小生成树)
- Eclipse 调整代码颜色的地方
- 公布windows的&;quot;Universal Apps&;quot; Unity3D游戏
- Linux中git的使用
- Leetcode 804. Unique Morse Code Words 莫尔斯电码重复问题
- [Swift]LeetCode725. 分隔链表 | Split Linked List in Parts
- 第四节:MVC中AOP思想的体现(四种过滤器)并结合项目案例说明过滤器的实际用法
- Jarvis OJ A Piece Of Cake
- win平台下Path变量消失问题
- cocos2d-x 开发用到的工具
- MySQL配置文件以及服务的开启关闭重启
- android 巧用动画使您app风骚起来
- sublime text3 (Mac) 快捷键
- window 10 javac不是内部或外部命令
热门文章
- HDU2837 Calculation(扩展欧拉定理)
- flask实现基于elasticsearch的关键词搜索建议
- 事件监听和window.history以及自定义创建事件
- IBM Rational Software Architect V9.0安装图解
- 关于Mysql唯一索引的操作方法(添加删除)
- 【JavaScript】jQuery绑定事件
- 生产-消费模式的synchronized和lock实现(十)
- MySQL的备份
- BZOJ 1441: Min(裴蜀定理)
- 使用postMan测试insert或者update接口