问题: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);
     }
     ;
 }

最新文章

  1. LDAP 中 CN, OU, DC 的含义
  2. Java Hour 51 CheckStyle
  3. 【ubuntu】install openbox+tint2+bmenu on ubuntu12.04.4
  4. 【Unique Binary Search Trees】cpp
  5. input输入框的各种样式
  6. java_Cookies_1_商品浏览历史记录servlet1
  7. 神器-Sublime Text 3 代码编辑器安装与使用
  8. React-Native OpenGL体验二
  9. Android设置背景
  10. UberX及以上级别车奖励政策(优步北京第二、三组)
  11. 玩转UITableView系列(一)--- 解耦封装、简化代码、适者生存!
  12. hadoop各个名词的理解
  13. PHP5.6+7代码性能加速-开启Zend OPcache-优化CPU
  14. Android 异步消息处理机制前篇(二):深入理解Message消息池
  15. 【刷水】之USACO2008资格赛(Bzoj1599-1603)
  16. easyUI使用datagrid-detailview.js实现多级级列表嵌套
  17. Perl构建和打包自己的模块
  18. 什么是Zookeeper?
  19. Python列表详解
  20. Android短信监听实现,及Android4.4之后短信机制变更

热门文章

  1. 使用C# DES解密java DES加密的字符串
  2. Light OJ 1314 Names for Babies
  3. 疯狂delphi - 朱建强 (一些小例子很实用,也是我所关心的几个问题)
  4. 在WPF中使用AForge.net控制摄像头拍照
  5. [置顶] 单片机C语言易错知识点经验笔记
  6. 关于bootstrap--网格系统
  7. 用Scrapy写一个爬虫
  8. hdu 4135 Co-prime(容斥)
  9. 如何安装CocoaPods
  10. NOTIFYICONDATA结构