1469 courses.cpp

各种算法

#include <memory.h>
#include <stdio.h>
//分别定义左右最大元素
#define LEFT_MAX 101
#define RIGHT_MAX 301
bool useif[RIGHT_MAX];
//link[]记录与右边元素连接的元素，-1表示没有连接
int link[RIGHT_MAX];
//定义左右两边元素
int left_num,right_num;
//array定义左右两边元素是否有连接
bool array[LEFT_MAX][RIGHT_MAX];
bool can(int t)
{
    int i;
    for(i = 0;i < right_num; i++)
    {
       if(!useif[i]&&array[t][i])
       {
           useif[i]=true;
           if(link[i]==-1||can(link[i]))
           {
              link[i]=t;
              return true;
           }
       }
    }
    return false;
}
int main()
{
    int i,j,k,num;int set;int p,n;
	scanf("%d",&set);
	while(set--)
	{
		scanf("%d%d",&p,&n);
		memset(link,-1,sizeof(link));
		memset(array,0,sizeof(array));
		left_num = p; right_num = n;
		for(i = 0;i < p;i++)
		{	int t;
			scanf("%d",&t);
			for(j = 0;j < t;j++)
			{	scanf("%d",&k);
				array[i][k-1] = true;
			}
		}
		num = 0;
		//匹配，num为结果
		for(i = 0;i < left_num; i++)
		{
			memset(useif,0,sizeof(useif));
			if(can(i)) num++;
		}
		if(num == p) printf("YES\n");
		else printf("NO\n");
	}
    return 1;
}