1466_girls and boys.cpp

各种算法

/*	
	最小顶点覆盖　＝　最大匹配
	本题求n --> n的最小顶点覆盖的补集
	即男女生两两之间没有暧昧关系的最大集合
 */
#include"memory.h"
#include"stdio.h"
#define L_MAX 501
#define R_MAX 501
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 i,j,k;int r;
	while(scanf("%d",&l_num) != EOF)
	{	r_num = l_num;
		memset(array,0,sizeof array);
		for(i = 0;i < l_num;i++){
			scanf("%d: (%d)",&j,&r);
			while(r--)
			{	scanf(" %d",&k);
				array[j][k] = 1;
			}
		}
		printf("%d\n",r_num - hungary()/2);//hungary必为偶数
	}
	return 1;
}