题目大意:在大学里有许许多多的课程,现在小明需要去选择课程,他是一个爱学习的人,所以想尽可能多的选择课程,
在学校里有n个课程,并且在学校规定,每周里的每天有12节课,那么一周就有7*12节课。
输入第一行为n,代表有n个课程
接下来n行,每行第一个数字x代表这个课程在这一周里面需要上x次。
然后跟着x对数字,第一个D代表这周的哪一天,第二个C代表这天的哪一节课
如果几个课程都在那d天的那c节课上课,那么你需要选择其中的一个,而不能选择多个课程
现在要求算出小明最多可以选择多少个课程.(题意翻译来自http://blog.csdn.net/wangjian8006/article/details/8004910)
题解:此题为求二分图最大匹配的匈牙利算法,弄清匈牙利算法以后本来此题是没有压力的水题,但是我竟然WA了一下午。。。。。 就错在循环范围上。。。。
#include<iostream> using namespace std; #define NUMMAX 310 int map[NUMMAX][NUMMAX]; int vis[NUMMAX]; int isWho[NUMMAX]; int n,m; int init() { if(scanf("%d",&n)==EOF) return 0; memset(map,0,sizeof(map)); for(int i=0;i<n;i++) { int t; scanf("%d",&t); while(t--) { int w,c; scanf("%d%d",&w,&c); int temp=(w-1)*12+c; map[i][temp]=1; } } memset(isWho,-1,sizeof(isWho));//初始化isWho数组 return 1; } int dfs(int x) { for(int i=1;i<=7*12;i++)//这里一定是等号 因为map[i][temp]的temp的范围是1-7*12 { if(map[x][i]&&!vis[i]) { vis[i]=1; if(isWho[i]==-1||dfs(isWho[i])) { isWho[i]=x; return 1; } } } return 0; } int main() { while(init()) { int ans=0; for(int i=0;i<n;i++) { memset(vis,0,sizeof(vis)); if(dfs(i)) ans++; } printf("%d\n",ans); } return 0; }
相关推荐
3. POJ2239: Li Ming的选课问题仍然是二分图最大匹配的应用。课程和时间点构成二分图的两部分,如果一门课程在某个时间点上课,就连接这两个节点。目的是计算每周Li Ming最多能上多少门不同的课程。 4. POJ2536: 地...
### ACM讲课之二分图匹配匈牙利算法学习教案知识点详解 #### 一、二分图的基本概念 二分图是一种特殊的图结构,在离散数学领域有着广泛的应用。所谓二分图,指的是能够将图的所有顶点划分为两个互不相交的集合V1和...
匈牙利算法主要应用于寻找二分图中的最大匹配,即在这个图中找到最大的两两不相交的边的集合。 #### 二、关键概念 1. **二分图**:由两个互不相交的顶点集组成的图,图中的每条边都连接着这两个集合中的节点。 - ...
- 二分图的最大匹配:如匈牙利算法,用于解决二分图的匹配问题,如`poj3041, poj3020`。 - **数据结构** - 字符串处理:如KMP算法和后缀数组,用于字符串搜索和模式匹配,如`poj1035, poj3080`。 - 排序算法:如...
- 二分图匹配问题通常通过匈牙利算法(Hungarian Algorithm)来解决。 #### 三、数据结构 1. **堆** - 推荐题目:[poj1035](https://vjudge.net/problem/POJ-1035)、[poj3080]...
- 二分图的最大匹配:匈牙利算法,如POJ3041。 - 最大流:KM算法,如POJ1459。 3. **数据结构** - 串:处理字符串问题,如POJ1035。 - 排序:快速排序、归并排序和堆排序,如POJ2299。 - 并查集:处理不相交...
- **匈牙利算法**:解决二分图匹配问题的一种经典算法。 #### 1094 Sorting It All Out - Floyd 或拓扑排序 - **知识点**: - **Floyd算法**:用于解决所有顶点对之间的最短路径问题。 - **拓扑排序**:对于有...
- **定义**: 使用匈牙利算法找到二分图中最大的匹配集合。 - **应用场景**: 适用于配对问题。 - **示例题目**: POJ 3041, POJ 3020 - **注意事项**: 理解匈牙利算法的基本思想和实现过程。 **6. 最大流的增广路...
- **匹配问题**:如匈牙利算法(Hungarian Method),适用于解决二分图的最大匹配问题。 - 示例题目:POJ 1459, POJ 3436 ##### 3. 动态规划 - **状态压缩**:通过状态压缩技术可以有效减少动态规划的状态数量。 ...
- **二分图最大匹配**:匈牙利算法,如poj3041和poj3020,解决分配问题。 - **最大流的增广路算法**:KM算法,如poj1459和poj3436,用于寻找网络中能传输的最大流量。 3. **数据结构**: - **字符串处理**:如...
- **匈牙利算法(KM算法)**:用于求解二分图的最大匹配问题。 - 示例题目:poj1459, poj3436 #### 数据结构 1. **链表、队列等基本数据结构** - 示例题目:poj1035, poj3080, poj1936 2. **树形结构** - ...
- **匈牙利算法**:一种高效的匹配算法,可以在多项式时间内找到一个二分图的最大匹配。 ### 三、数据结构 #### 1. 队列 - **内容**: 包括队列的基本操作如入队、出队等。 - **示例题目**: poj1035, poj3080, ...
5. **二分图匹配**:匈牙利算法或Kuhn-Munkres算法用于求解二分图的最大匹配问题,广泛应用于配对问题。 6. **网络流**:包括Ford-Fulkerson算法和Edmonds-Karp算法,它们用于寻找网络中最大流量,可以解决很多实际...
- **二分图最大匹配**:匈牙利算法,如 poj3041、poj3020。 - **最大流**:KM 算法求解,如 poj1459、poj3436。 3. **数据结构**: - **字符串**:处理字符串问题,如 poj1035、poj3080。 - **排序**:快速排序...
- **二分图最大匹配**:学习匈牙利算法,如Poj3041、Poj3020。 - **最大流**:掌握KM算法,如Poj1459、Poj3436。 3. **数据结构** - **字符串**:学习字符串处理和操作,如Poj1035、Poj3080等。 - **排序**:...
* 二分图的最大匹配:匈牙利算法 + poj3041, poj3020 * 最大流的增广路算法:KM算法 + poj1459, poj3436 三、数据结构 * 串:poj1035, poj3080, poj1936 * 排序:快排、归并排、堆排 + poj2388, poj2299 * 简单...
- (poj1459, poj3436):例如匈牙利算法(KM算法),用于解决二分图的最大匹配问题。 ### 三、数据结构 1. **链表、栈、队列**: - (poj1035, poj3080, poj1936):基本的数据结构及其应用场景。 2. **树**: - ...
5. 二分图最大匹配:匈牙利算法的应用,如POJ3041、POJ3020。 6. 最大流:Kuhn-Munkres算法,如POJ1459、POJ3436。 三、数据结构 1. 串:字符串处理,如POJ1035、POJ3080、POJ1936。 2. 排序:快速排序、归并排序、...
(5) 二分图的最大匹配:匈牙利算法 (6) 最大流的增广路算法:KM算法 三、数据结构 本部分涵盖了数据结构,包括串、排序、简单并查集的应用、哈希表和二分查找等高效查找法、哈夫曼树和堆、trie树。 (1) 串:poj...
KM 最大时,要求改动最少**、**【HDU 3523】My Brute 求 KM 最大时,要求改动最少**:这些题目中的“KM”可能不是指KMP算法,而是指Kuhn-Munkres算法(也称匈牙利算法),用于解决赋权二分图的最大匹配问题,目标是在...