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

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

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

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

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 int p, n;
 7 int G[305][305];
 8 int vis[305];
 9 int match[305];    //第i学生的选课
10 
11 int dfs(int x)
12 {
13     for (int i = 1; i <= n; i++)
14     {
15         if (G[x][i] && !vis[i])
16         {
17             vis[i] = 1;   //标记，为了为了后面改课时跳过这门课
18             if (!match[i] || dfs(match[i]))   //如果该学生还没有确定课或者这门课换一个学生
19             {
20                 match[i] = x;
21                 return 1;
22             }
23         }
24     }
25     return 0;
26 }
27 
28 int main()
29 {
30     //freopen("D:\txt.txt", "r", stdin);
31     int T;
32     int a;
33     cin >> T;
34     while (T--)
35     {
36         memset(match, 0, sizeof(match));
37         memset(G, 0, sizeof(G));
38         cin >> p >> n;
39         int num;
40         for (int i = 1; i <= p; i++)
41         {
42             cin >> num;
43             while (num--)
44             {
45                 cin >> a;
46                 G[i][a] = 1;
47             }
48         }
49         //为每门课匹配学生
50         int i;
51         for (i = 1; i <= p; i++)
52         {
53             memset(vis, 0, sizeof(vis));
54             if (!dfs(i))  break;
55         }
56         if (i == p + 1)   cout << "YES" << endl;
57         else cout << "NO" << endl;
58     }
59 }