1364_machine schedule.cpp

来自「各种算法」· C++ 代码 · 共 50 行

/*	zju 1364 Machine Schedule
	最小顶点覆盖　＝　最大匹配
 */
#include"memory.h"
#include"stdio.h"
#define L_MAX 101
#define R_MAX 101
bool ckd[R_MAX];
int link[R_MAX];
int l_num,r_num;
bool array[L_MAX][R_MAX];
bool augment_path(int t)//找交错路径
{
	for(int i = 0;i < r_num; i++)
	{	if(!ckd[i] && array[t][i]){
			ckd[i] = true;
			if(link[i] == -1 || augment_path(link[i])){
				link[i] = t;
				return true;
			}
		}
	}
	return false;
}
int hungary()//匈牙利算法
{	
	memset(link,-1,sizeof link);
	int num = 0;
	for(int i = 0;i < l_num;i++){
		memset(ckd,0,sizeof ckd);
		if(augment_path(i)) num++;
	}
	return num;
}
int main()
{	int k;int f,x,y;
	while(scanf("%d%d%d",&l_num,&r_num,&k) != EOF && l_num != 0)
	{	
		memset(array,0,sizeof array);
		while(k--)
		{	
			scanf("%d%d%d",&f,&x,&y);
			if(x != 0 && y != 0)
			array[x][y] = 1;
		}
		printf("%d\n",hungary());
	}
	return 1;
}