本文主要是介绍POJ2239 Selecting Courses(二分图),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题意
一周7天,每天12节课,现在学校有n种课程可以选择,每种课程给出对应的时间(有的课一周内有好几节),要求选的课没有时间冲突,求最大选课数。
要点:
知道是二分图就简单了,没有冲突不就二分图最大匹配嘛,将n节课作为u,所有时间作为v,因为数据比较小,所以建图直接用三维数组,这题如果一开始不知道是二分图估计很难办,知道了就是个裸题。
15486482 | Seasonal | 2239 | Accepted | 436K | 63MS | C++ | 792B | 2016-05-09 22:19:38 |
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int map[305][15][15], used[15][15], girl[15][15];
int n;bool find(int x)
{int i,j;for (i = 1; i < 15; i++)for (j = 1; j < 15; j++){if (map[x][i][j] && !used[i][j]){used[i][j] = 1;if (girl[i][j] == -1 || find(girl[i][j])){girl[i][j] = x;return true;}}}return false;
}int main()
{int i,num,x,y;while (scanf("%d", &n) != EOF){memset(map, 0, sizeof(map));memset(girl, -1, sizeof(girl));for (i = 1; i <= n; i++){scanf("%d", &num);while (num--){scanf("%d%d", &x, &y);map[i][x][y] = 1;}}int ans = 0;for (i = 1; i <= n; i++){memset(used, 0, sizeof(used));if (find(i)) ans++;}printf("%d\n", ans);}return 0;
}
这篇关于POJ2239 Selecting Courses(二分图)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!