poj2239-二分图最大匹配匈牙利算法

题目大意:在大学里有许许多多的课程，现在小明需要去选择课程，他是一个爱学习的人，所以想尽可能多的选择课程，
在学校里有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;
}