POJ 3692 二分图最大独立点集

题意：

给出女生人数 G 男生人数 B 和男女认识的关系数 M

接下来 M 行..

a b 表示女生 a 和男生 b 认识..

当G B M都等于0的时候表示输入结束..

输出可以找出多少个人是互相认识的..

P.S. 男生们都互相认识了~女生们也都互相认识了..

思路：

将男生看成一个集合女生看成一个集合

先求补图

然后最大独立及顶点个数 = 节点数(x + y) - 最大匹配数

所以我就是先把他们当成都是认识的了..

如果是认识的就变成 G[a][b] = false;

然后用匈牙利求最大匹配..

Tips：

主要是最大独立点集这个概念和求的方法~

囧~如果我能够自己想出来就好了~~

Code：

View Code

 1 #include <stdio.h>
 2 #include <cstring>
 3 #define clr(x) memset(x, 0, sizeof(x))
 4 
 5 int v1, v2;
 6 bool G[210][210];
 7 bool vis[210];
 8 int link[210];
 9 int sum;
10 
11 bool dfs(int x)
12 {
13     for(int y = 1; y <= v2; ++y)
14         if(G[x][y] && !vis[y]){
15             vis[y] = true;
16             if(link[y] == 0 || dfs(link[y])){
17                 link[y] = x;
18                 return true;
19             }
20         }
21     return false;
22 }
23 
24 void search()
25 {
26     clr(link);
27     sum = 0;
28     for(int x = 1; x <= v1; ++x){
29         clr(vis);
30         if(dfs(x))
31             sum++;
32     }
33     return;
34 }
35 
36 
37 int main()
38 {
39 
40     int i, j, k = 0;
41     int  a, b, m;
42     while(scanf("%d %d %d", &v1, &v2, &m) != EOF)
43     {
44         memset(G, true, sizeof(G));
45 
46         if(v1 == 0 && v2 == 0 && m == 0) break;
47         while(m--)
48         {
49             scanf("%d %d", &a, &b);
50             G[a][b] = false;
51         }
52         search();
53         printf("Case %d: %d\n", ++k, v1+v2-sum);
54     }
55     return 0;
56 }