【二分匹配】HDU1083-Courses

Courses
Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 3645    Accepted Submission(s): 1745

Problem Description
Consider a group of N students and P courses. 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:

. 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

Your program should read sets of data from a text file. The first line of the input file contains the number of the data sets. Each data set is presented in the following format:

P N
Count1 Student1 1 Student1 2 ... Student1 Count1
Count2 Student2 1 Student2 2 ... Student2 Count2
......
CountP StudentP 1 StudentP 2 ... StudentP CountP

The first line in each data set contains two positive integers separated by one blank: P (1 <= P <= 100) - the number of courses and N (1 <= N <= 300) - the number of students. The next P lines describe in sequence of the courses . from course 1 to course
P, each line describing a course. The description of course i is a line that starts with an integer Count i (0 <= Count i <= N) representing the number of students visiting course i. Next, after a blank, you'll find the Count i students, visiting the course,
each two consecutive separated by one blank. Students are numbered with the positive integers from 1 to N.

There are no blank lines between consecutive sets of data. Input data are correct.

The result of the program is on the standard output. For each input data set the program prints on a single line "YES" if it is possible to form a committee and "NO" otherwise. There should not be any leading blanks at the start of the line.

An example of program input and output:
 

Sample Input
2
3 3
3 1 2 3
2 1 2
1 1
3 3
2 1 3
2 1 3
1 1
 

Sample Output
YES
NO
 

Source
Southeastern Europe 2000
 

p门课，每门课有若干名学生喜欢，一共有N个学生，每个学生可以喜欢多门课，写出每门课以及喜欢这门课的学生，
求是否能为所有的课安排班长（一个人只能任命为一门课的班长），如果能输出“YES”，不能输出“NO”
思路：
将学生看成A集合，课程看成B集合，即求A集合中给的元素（数量可多于B集合）是否能够
完全匹配上B集合的所有元素（每个A只能和B中某些元素匹配）
明显的二分匹配，用匈牙利算法
AC代码：

#include<stdio.h>
#include<string.h>
int course[510],flag[510],line[510][510];//被HDU坑了，数组显然比100和300要大才能AC
int n,m;
int Find(int x)
{
    int i;
    for(i=1;i<=m;i++)//遍历所有被选课
    {
       if(line[x][i]==1&&flag[i]==0)
       {//如果 x喜欢i课且在这一个递归选取阶段没有被选取（哪怕是暂时选取，新的递归可能会换）
          flag[i]=1;//标记被选取
          if(course[i]==0||Find(course[i]))//如果被选课没有班长或它的班长可以调换（它的班长可以选择其它被选课）
          {
             course[i]=x;//将i课的班长定为 x
             return 1;
          }
       }
    }
    return 0;
}
int main()
{
    int i,j,T,x,y,k,sum;
    scanf("%d",&T);
    while(T--)
    {
       scanf("%d %d",&m,&n);//m是课程数，n是学生数目，别弄反了！！！
       memset(line,0,sizeof(line));
       memset(course,0,sizeof(course));
       for(i=1;i<=m;i++)
       {
          scanf("%d",&x);
          while(x--)
          {
             scanf("%d",&y);
             line[y][i]=1;//表示 y学生喜欢 i课
          }
       }
       sum=0;//记录能选的班长数
       for(i=1;i<=n;i++)
       {
          memset(flag,0,sizeof(flag));//每次都要清 0
          if(Find(i)) sum++;//找到一对就记录
       }

       if(sum==m)
       printf("YES\n");
       else
       printf("NO\n");
    }
    return 0;
}