HDU

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1083

题意：给你P个课程，并且给出每个课程的学生，求出学生与课程的最大匹配数目，问结果是否与课程数目相同，相同输出YES，否则NO

分析：匈牙利算法

1.每个学生选的都是不同的课(即不能有两个学生选同一门课)

2.每门课都有一个代表(即P门课都被成功选过)

求解二部图的最大匹配。只要匹配可以盖住每门课程，即匹配数与课程数量相等，委员会就可以组成。

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

AC代码：

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #include<queue>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<iostream>
 8 
 9 using namespace std;
10 typedef long long LL;
11 
12 #define INF 0x3f3f3f3f
13 #define N 420
14 #define MAXN 100000000
15 #define mod 1000000007
16 
17 int maps[N][N],n,p,v[N],vis[N];///vis[i]表示y集合中的点是否匹配；
18 
19 int Hungary(int s)
20 {
21     int i;
22     for(i=1;i<=p;i++)
23         if(v[i]==0&&maps[s][i]==1)
24     {
25         v[i]=1;
26         if(vis[i]==0||Hungary(vis[i])==1)
27         {
28             vis[i]=s;
29             return 1;
30         }
31     }
32     return 0;
33 }
34 
35 int main()
36 {
37     int T,m,i,j,x;
38 
39     scanf("%d", &T);
40 
41     while(T--)
42     {
43         memset(vis,0,sizeof(vis));
44         memset(maps,0,sizeof(maps));
45 
46         scanf("%d %d", &p,&n);
47 
48         for(i=1;i<=p;i++)
49         {
50             scanf("%d",&m);
51 
52             for(j=1;j<=m;j++)
53             {
54                 scanf("%d", &x);
55                 maps[x][i]=1;
56             }
57         }
58         int ans=0;
59         for(i=1;i<=n;i++)///
60         {
61             memset(v,0,sizeof(v));
62             if(Hungary(i))
63                 ans++;
64         }
65         if(ans==p)
66             printf("YES
");
67         else
68             printf("NO
");
69     }
70     return 0;
71 }