poj-1469-COURSES-二分图匹配-匈牙利算法(模板)
2024-08-31 21:09:47
题意:N个学生,P个课程,问能不能找到课程的P个匹配。
思路:【早上睡醒了再写】
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = ;
int n, p;
vector<int> g[maxn];
int from[maxn], tot;
bool use[maxn]; bool match(int x)
{
for (int i = ; i < g[x].size(); i ++) {
if(!use[g[x][i]]) {
use[g[x][i]] = true;
if(from[g[x][i]] == - || match(from[g[x][i]])) {
from[g[x][i]] = x;
return true;
}
}
}
return false;
} int hungary()
{
tot = ;
memset(from, -, sizeof(from));
for(int i = ; i <= n; i ++) {
memset(use, , sizeof(use));
if(match(i)) tot ++;
}
return tot;
} int main()
{
int t; cin>>t;
while(t--) {
for(int i = ; i < maxn; i++) g[i].clear();
scanf("%d%d", &p, &n);
for(int i = ; i <= p; i++) {
int k; scanf("%d", &k);
for(int j = ; j < k; j++) {
int a; scanf("%d", &a);
g[i].push_back(a);
}
}
int res = hungary();
//cout<<res<<endl;
if(res == p) printf("YES\n");
else printf("NO\n");
}
}
最新文章
- iOS音乐播放器相关
- 新手用git
- Objective-C NSData与实现NSCoding协议进行序列化和反序列化
- Export Data from mysql Workbench 6.0
- N的阶乘末尾0的个数和其二进制表示中最后位1的位置
- mysql 不允许连接
- 【ubuntu】中文输入法安装二三事
- scrollview中套listView的问题,记录一下。
- hibernate中的session缓存
- Never use GetDate() when comparing date timesoffsets, use SYSDATETIMEOFFSET()
- Python之路第六天,进阶-算法
- 关于Resharper的使用经验
- VR全景智慧城市-VR大时代
- Disruptor——一种可替代有界队列完成并发线程间数据交换的高性能解决方案
- 201521123070 《JAVA程序设计》第6周学习总结
- Linux下php安装redis扩展(redis已经安装)
- Idea使用Maven创建Java Web项目
- nodeJS安装和环境变量的配置
- SSL 链接安全协议的enum
- [译]Godot系列教程六 - 简单的二维游戏
热门文章
- 【BZOJ】【4002】【JLOI2015】有意义的字符串
- 客户端发包 GS端接收
- __cdecl __stdcall __fastcall之函数调用约定讲解
- GIS数据格式topojson
- MVC模式在游戏开发的应用
- delphi 网络函数
- HDU 3255 Farming (线段树+扫面线,求体积并)
- 有了 Docker,用 JavaScript 框架开发的 Web 站点也能很好地支持网络爬虫的内容抓取
- Windows 7 常用快捷键 命令
- BZOJ 1218: [HNOI2003]激光炸弹 前缀DP