Consider a group of N students and P courses.
有N个学生,P门课
Each student visits zero,
one or more than one courses.
每一个学生学习一些课程。
Your task is to determine whether it is possible to form a committee of exactly P students that satisfies simultaneously the conditions:
你的任务是判断是否能可能P个学习符合下面的情况。
. every student in the committee represents a different course (a student can represent a course if he/she visits that course)
每一个学生参加不同的课程
. each course has a representative in the committee
每一个课程都有学生参加。
解题报告:因为课程有P个,而且只选择P个学生,每一个学生加参的课程不同,而且每一门课都
有学生参加,这就是说有P个学生和这P门课一一对应,也就是最大二分匹配问题。
#include
#include
int cours[101];
int stu[301];
int adj[101][301];
int m[301];
int p,n;
int DFS(int from)
{
int i;
for(i=1;i<=n;i++)
{
if(adj[from][i]==1&&m[i]==0)
{
m[i]=1;
if(stu[i]==-1||DFS(stu[i]))
{
stu[i]=from;
cours[from]=i;
return 1;
}
}
}
return 0;
}
int main()
{
int i,t,temp,j;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&p,&n);
memset(cours,-1,sizeof(cours));
memset(stu,-1,sizeof(stu));
memset(adj,0,sizeof(adj));
for(i=1;i<=p;i++)
{
scanf("%d",&temp);
while(temp--)
{
scanf("%d",&j);
adj[i][j]=1;
}
}
for(i=1;i<=p;i++)
{
if(cours[i]==-1)
{
memset(m,0,sizeof(m));
if(DFS(i)==0)
break;
}
}
if(i>p)
printf("YES\n");
else
printf("NO\n");
}
}