POJ2239 二分图最大匹配
2024-10-11 13:16:50
问题:POJ2239
分析:
本题给出每门课程的上课时间,求最大选课数,可以转化为二分图最大匹配问题求解。
设集合A为课程集,集合B为上课时间集,根据输入建立二分图。最大选课书就是该二分图的最大匹配数,采用匈牙利算法即可解决。
AC代码
//Memory: 252K Time: 16MS #include <iostream> #include <cstring> #include <cstdio> using namespace std; ; ; int edge[maxc][maxl]; int ne[maxc]; int match[maxl]; bool vis[maxl]; int n, t; int a, b; bool findPath(int start) { ; i < ne[start]; i++){ int current = edge[start][i]; if (vis[current]) continue; vis[current] = ; if ( !match[current] || findPath(match[current]) ){ match[current] = start; return true; } } return false; } int solve() { memset(match, , sizeof(match)); ; ; i <= ; i++) { memset(vis, , sizeof(vis)); if (findPath(i)) cnt++; } return cnt; } void input() { memset(edge, , sizeof(edge)); memset(ne, , sizeof(ne)); ; i < n; i++){ scanf("%d", &t); while (t--){ scanf("%d%d", &a, &b); ) * + b; edge[ class_num ][ ne[class_num]++ ] = i; } } } int main() { while ( ~scanf("%d", &n) ){ input(); int ans = solve(); printf("%d\n", ans); } ; }
最新文章
- LDAP 中 CN, OU, DC 的含义
- Java Hour 51 CheckStyle
- 【ubuntu】install openbox+tint2+bmenu on ubuntu12.04.4
- 【Unique Binary Search Trees】cpp
- input输入框的各种样式
- java_Cookies_1_商品浏览历史记录servlet1
- 神器-Sublime Text 3 代码编辑器安装与使用
- React-Native OpenGL体验二
- Android设置背景
- UberX及以上级别车奖励政策(优步北京第二、三组)
- 玩转UITableView系列(一)--- 解耦封装、简化代码、适者生存!
- hadoop各个名词的理解
- PHP5.6+7代码性能加速-开启Zend OPcache-优化CPU
- Android 异步消息处理机制前篇(二):深入理解Message消息池
- 【刷水】之USACO2008资格赛(Bzoj1599-1603)
- easyUI使用datagrid-detailview.js实现多级级列表嵌套
- Perl构建和打包自己的模块
- 什么是Zookeeper?
- Python列表详解
- Android短信监听实现,及Android4.4之后短信机制变更