POJ2239 Selecting Courses(二分图)

题意

一周7天，每天12节课，现在学校有n种课程可以选择，每种课程给出对应的时间（有的课一周内有好几节），要求选的课没有时间冲突，求最大选课数。

要点：

知道是二分图就简单了，没有冲突不就二分图最大匹配嘛，将n节课作为u，所有时间作为v，因为数据比较小，所以建图直接用三维数组，这题如果一开始不知道是二分图估计很难办，知道了就是个裸题。

#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;
}