hdu1068 Girls and Boys 基础匈牙利

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cstdlib>
 5 using namespace std;
 6 
 7 #define MAXN 500
 8 int map[MAXN][MAXN];
 9 int mark[MAXN];
10 int pipei[MAXN];
11 int n;
12 
13 int search(int a)
14 {
15     for (int i = 0; i < n; i++)
16     {
17         if (map[a][i] && !mark[i])
18         {
19             mark[i] = 1;
20             if (pipei[i] == -1 || search(pipei[i]))
21             {
22                 pipei[i] = a;
23                 return 1;
24             }
25         }
26     }
27 
28     return 0;
29 }
30 
31 int main()
32 {
33     while (~scanf("%d",&n))
34     {
35         memset(map, 0, sizeof(map));
36         int m;
37         for (int i = 0; i <n; i++)
38         {
39             int y;
40             scanf("%d: (%d)", &m, &y);
41             for (int i = 0; i < y; i++)
42             {
43                 int a;
44                 scanf("%d", &a);
45                 map[m][a] = 1;
46             }
47         }
48 
49         memset(pipei, -1, sizeof(pipei));
50         int ans1 = 0;
51         for (int i = 0; i < n; i++)
52         {
53             memset(mark, 0, sizeof(mark));
54             if (search(i))
55                 ans1++;
56         }
57         printf("%d
", n - ans1/2);
58     }
59     //system("pause");
60     return 0;
61 }