HDU1068 Girls and Boys

　　本题求最大独立集，那么用公式：

　　最大独立集 = 总结点数 - 最大匹配

　　对于这道题来说，发现给出的数据构造出的是一个无向图，那么直接匈牙利计算会重复，得出的是2倍的最大匹配。所以最后结果得出的最大匹配值要除以2.

View Code

 1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4 using namespace std;
 5 
 6 const int M = 500 + 2;
 7 bool g[M][M], vis[M];
 8 int  link[M], m, n, k;
 9 
10 bool find(int i)
11 {
12     for(int j = 0;j < n; j++)
13     {
14         if(g[i][j] && !vis[j])
15         {
16             vis[j] = true;
17             if(link[j] == -1 || find(link[j]))
18             {
19                 link[j] = i;
20                 return true;
21             }
22         }
23     }
24     return false;
25 }
26 
27 int main()
28 {
29     int i, j, res;
30     while(scanf("%d", &n) == 1)
31     {
32         memset(g, false, sizeof(g));
33         memset(link, -1, sizeof(link));
34         for(int p= 0; p < n; p ++)
35         {
36             scanf("%d: (%d) ", &j, &m);
37             for(i = 0; i < m; i ++)
38             {
39                 scanf("%d", &k);
40                 g[j][k] = true;
41             }
42         }
43         for(res=0, i = 0; i < n; i++)
44         {
45             memset(vis,0,sizeof vis);
46             if(find(i))
47                 res++;
48         }
49         printf("%d\n", n - res/2);
50     }
51     return 0;
52 }