HDU 1068 Girls and Boys

题目大意：

有一些男女生之间的暧昧关系，求找到一组人数最多的，组中任何两人都没有暧昧关系的情况‘

直接建图，求一个最大独立集

二分图中最大独立集 = 总数 - 最大匹配数

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 using namespace std;
 5 const int N = 1005;
 6 int g[N][N] , cx[N] , cy[N] , visy[N] , n;
 7 
 8 int dfs(int u)
 9 {
10     for(int i=0 ; i<n ; i++){
11         if(g[u][i] && !visy[i]){
12             visy[i] = 1;
13             if(cy[i] == -1 || dfs(cy[i])){
14                 cx[u] = i;
15                 cy[i] = u;
16                 return 1;
17             }
18         }
19     }
20     return 0;
21 }
22 
23 int MaxMatch()
24 {
25     int ans = 0;
26     memset(cx , -1 , sizeof(cx));
27     memset(cy , -1 , sizeof(cy));
28     for(int i=0 ; i<n ; i++){
29         if(cx[i] == -1){
30             memset(visy , 0 , sizeof(visy));
31             ans += dfs(i);
32         }
33     }
34     return ans;
35 }
36 
37 int main()
38 {
39    // freopen("a.in" , "r" , stdin);
40     while(scanf("%d" , &n) == 1)
41     {
42         int id , k , match;
43         memset(g , 0 , sizeof(g));
44         for(int i=0 ; i<n ; i++){
45             scanf("%d: (%d)" , &id , &k);
46             for(int j=0 ; j<k ; j++){
47                 scanf("%d" , &match);
48                 g[id][match] = 1;
49             }
50         }
51         printf("%d
" , n-MaxMatch()/2);//因为男女生重复匹配了，所以要除以2
52     }
53     return 0;
54 }