题意

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

要点：

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

15486482

Accepted

436K

63MS

792B

2016-05-09 22:19:38

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