hdu1068 Girls and Boys

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

二分图的最大独立集数=节点数（n）— 最大匹配数（m）

另外需要注意的是：

本题求出的最大匹配数是实际的两倍需要m/2

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<math.h>
 4 #include<string.h>
 5 #include<stdlib.h>
 6 using namespace std;
 7 const int N=510;
 8 int a[N][N];
 9 int match[N];
10 int use[N];
11 int n;
12 int dfs(int u)
13 {
14     for(int i=0;i<n;i++)
15     {
16         if(a[u][i] && !use[i])
17         {
18             use[i]=1;
19             if(match[i]==-1 || dfs(match[i]))
20             {
21                 match[i]=u;
22                 return 1;
23             }
24         }
25     }
26     return 0;
27 }
28 int bipartite()
29 {
30     int res=0;
31     memset(match,-1,sizeof(match));
32     for(int i=0;i<n;i++)
33     {
34         memset(use,0,sizeof(use));
35         if(dfs(i))
36         res++;
37     }
38     return res;
39 }
40 int main()
41 {
42     //freopen("in.txt","r",stdin);
43     while(~scanf("%d",&n))
44     {
45         int q,p,m;
46         memset(a,0,sizeof(a));
47         for(int i=0;i<n;i++)
48         {
49             scanf("%d: (%d) ",&q,&m);
50             for(int j=0;j<m;j++)
51             {
52                 scanf("%d",&p);
53                 a[q][p]=1;
54             }
55         }
56         int x=n-bipartite()/2;
57         printf("%d
",x);
58     }
59     return 0;
60 }