hdu1150 Machine Schedule (二分圖的最小頂點覆寫)

題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=1150

最小點覆寫數： 最小覆寫要求用最少的點（Ｘ集合或Ｙ集合的都行）讓每條邊都至少和其中一個點關聯。可以證明：最少的點（即覆寫數）＝最大比對數

#include <stdio.h>    
#include <string.h>    
#define MAXN 102    

int map[MAXN][MAXN];    
int from[MAXN],used[MAXN];    
//二分圖的最小點覆寫數=最大比對數
int match(int x,int m)//匈牙利算法  
{    
	int i;    
	for(i=0;i<m;++i)   
	{    
		if(!used[i]&&map[x][i])    
		{    
			used[i]=1;    
			if(from[i]==-1||match(from[i],m))    
			{    
				from[i]=x; 
				return 1;    
			}    
		}    
	}    
	return 0;    
}    

int main()    
{    
	int k,n,m,sum,i,j,x,y;    
	while(scanf("%d",&n)&&n)    
	{    
		memset(map,0,sizeof(map));    
		memset(from,-1,sizeof(from));    
		sum=0;    
		scanf("%d %d",&m,&k);
		for(i=0;i<k;++i)
		{
			scanf("%d %d %d",&j,&x,&y);
			if(x&&y)//初始狀态機器處于mode_0狀态
				map[x][y]=1;
		}
		for(i=0;i<n;++i)   
		{    
			memset(used,0,sizeof(used));    
			if(match(i,m))    
				++sum;    
		}    
		printf("%d\n",sum);    
	}    
	return 0;    
}