HDU 1083 Courses（二分图匹配模板）

http://acm.hdu.edu.cn/showproblem.php?pid=1083

题意：
有p门课和n个学生，每个学生都选了若干门课，每门课都要找一个同学来表演，且一个同学只能表演一门课，判断是否能行。

思路：
二分图匹配的模板题。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 int p, n;

 int G[][];

 int vis[];

 int match[];    //第i学生的选课

 int dfs(int x)

 {

     for (int i = ; i <= n; i++)

     {

         if (G[x][i] && !vis[i])

         {

             vis[i] = ;   //标记，为了为了后面改课时跳过这门课

             if (!match[i] || dfs(match[i]))   //如果该学生还没有确定课或者这门课换一个学生

             {

                 match[i] = x;

                 return ;

             }

         }

     }

     return ;

 }

 int main()

 {

     //freopen("D:\\txt.txt", "r", stdin);

     int T;

     int a;

     cin >> T;

     while (T--)

     {

         memset(match, , sizeof(match));

         memset(G, , sizeof(G));

         cin >> p >> n;

         int num;

         for (int i = ; i <= p; i++)

         {

             cin >> num;

             while (num--)

             {

                 cin >> a;

                 G[i][a] = ;

             }

         }

         //为每门课匹配学生

         int i;

         for (i = ; i <= p; i++)

         {

             memset(vis, , sizeof(vis));

             if (!dfs(i))  break;

         }

         if (i == p + )   cout << "YES" << endl;

         else cout << "NO" << endl;

     }

 }