POJ 1466 二分图最大独立集.cpp

题意：

给出了男女之间的暧昧关系..求解有多少人之间是没有暧昧关系的..

先给n表示有n个同学

然后同学a:(暧昧关系人数m) 暧昧关系同学1 暧昧关系同学2 暧昧同学3 ...

思路：

求出最大独立集..

Tips：

有向图：最大独立集 = n-最大匹配

无向图：最大独立集 = n-最大匹配/2

Code：

View Code

 1 #include <stdio.h>
 2 #include <cstring>
 3 #define clr(x) memset(x, 0, sizeof(x))
 4 const int INF = 0x1f1f1f1f;
 5 
 6 struct Edge
 7 {
 8     int next;
 9     int to;
10 }edge[1000000];
11 int tot;
12 int head[510];
13 
14 void add(int s, int u)
15 {
16     edge[tot].to = u;
17     edge[tot].next = head[s];
18     head[s] = tot++;
19 }
20 
21 int link[510];
22 int vis[510];
23 int sum, n;
24 
25 int dfs(int x)
26 {
27     for(int i = head[x]; i != -1; i = edge[i].next){
28         int y = edge[i].to;
29         if(!vis[y]){
30             vis[y] = true;
31             if(link[y] == 0 || dfs(link[y])){
32                 link[y] = x;
33                 return true;
34             }
35         }
36     }
37     return false;
38 }
39 
40 void solve()
41 {
42     clr(link);
43     sum = 0;
44     for(int i = 0; i < n; ++i){
45         clr(vis);
46         if(dfs(i))
47             sum++;
48     }
49 }
50 
51 int main()
52 {
53     int i, j, k;
54     int a, b, m;
55     while(scanf("%d", &n) != EOF)
56     {
57         memset(head, 0xff, sizeof(head));
58         for(i = 0; i < n; ++i) {
59             scanf("%d: (%d)", &a, &m);
60             while(m--) {
61                 scanf("%d", &b);
62                 add(a, b);
63             }
64         }
65 
66         solve();
67 
68         printf("%d\n", n-sum/2);
69     }
70     return 0;
71 }