题目链接：

我之前不会最大二分匹配，先用的搜索来做（其实这条思路应该也是对的，因为题目给的时间比较宽），超时，而且感觉无法优化了。

后来看了别人的代码，发现原来要用最大二分匹配。

貌似解决最大二分匹配有两种途径：1，网络流；2，匈牙利算法。

我用的是匈牙利算法。

网上有很多关于匈牙利算法的文章，我这里就不再对算法做解释了。

有时候被迫地不求甚解，匈牙利算法的证明我就没有仔细研究，只是能实现罢了。

#include 
     
      #include 
      
       using namespace std;const int STUDENT_NUM = 305;const int COURSE_NUM = 105;//有多少个学生作为代表int augmentedPathsNum;//记录某个课程由哪个学生代表int mapping[COURSE_NUM];//处理一个学生的过程中，某个课程是否被访问过int isVisited[COURSE_NUM];//记录某个学生参加了哪些课程vector
       
         coursesAttend[STUDENT_NUM];//用深搜判断从studentId出发，是否存在增广路径int DFS_isAugmentedPathExist(int studentId){    for (int i = 0;i < coursesAttend[studentId].size();i ++)    {        int courseId = coursesAttend[studentId][i];        if (isVisited[courseId] != 0)            continue;        //被访问过        isVisited[courseId] = 1;        if (mapping[courseId] == -1 || DFS_isAugmentedPathExist(mapping[courseId]))        {            mapping[courseId] = studentId;            return 1;        }    }    return 0;}int main (){    int casesNum;    scanf("%d",&casesNum);    for (int i = 1;i <= casesNum;i ++)    {        int coursesNum, studentsNum;        scanf("%d%d", &coursesNum, &studentsNum);        for (int j = 1;j <= studentsNum;j ++)            coursesAttend[j].clear();        //课程编号为1~coutsesNum        for (int j = 1;j <= coursesNum;j ++)        {            int studentsNumOfCourse;            scanf("%d",&studentsNumOfCourse);            for (int k = 1;k <= studentsNumOfCourse;k ++)            {                int studentId;                scanf("%d",&studentId);                coursesAttend[studentId].push_back(j);            }        }        //mapping[i] = -1表示课程i还没有学生代表        memset(mapping, -1, sizeof(mapping));        augmentedPathsNum = 0;        for (int j = 1;j <= studentsNum;j ++)        {            memset(isVisited, 0, sizeof(isVisited));            if ( DFS_isAugmentedPathExist(j) == 1 )                augmentedPathsNum ++;        }        //每个课程都有学生代表        if (augmentedPathsNum == coursesNum)            printf("YES\n");        else            printf("NO\n");    }    return 0;}