HDU2444 The Accomodation of Students

　　二分图判定 + 最大匹配。

　　二分图判断方法——染色法：首先取一个点染成白色，然后将其相邻的点染成黑色，如果发现相邻的点已经被染成白色，即出现冲突，那么为这些集合不能构成二分图；如果直到所有点都染色后都无冲突，那么可以构成二分图。

View Code

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <vector>
 4 using namespace std;
 5 
 6 const int maxn = 200+5;
 7 int n, m;
 8 bool g[maxn][maxn];
 9 bool vis[maxn];
10 int link[maxn];
11 int color[maxn];  // 黑白染色法判二分图，0白色，1黑色
12 
13 void init()
14 {
15     memset(link, -1, sizeof link);
16     memset(g, false, sizeof g);
17     memset(color, -1, sizeof color);
18 }
19 
20 bool bfs(int s)
21 {
22     if(color[s] == -1)
23         color[s] = 0;
24     for(int i = 1; i <= n; i ++)
25     {
26         if(g[s][i])
27         {
28             if(color[i] == -1)
29                 color[i] = !color[s];
30             if(color[i] == color[s])
31                 return false;
32         }
33         
34     }
35     return true;
36 }
37 
38 bool find(int i)
39 {
40     for(int j = 1; j <= n; j ++)
41     {
42         if(g[i][j] && !vis[j])
43         {
44             vis[j] = true;
45             if(link[j] == -1 || find(link[j]))
46             {
47                 link[j] = i;
48                 return true;
49             }
50         }
51     }
52     return false;
53 }
54 
55 int main()
56 {
57     int a, b;
58     while(scanf("%d%d", &n, &m) == 2)
59     {
60         init();
61         for(int i = 1; i <= m; i ++)
62         {
63             scanf("%d%d", &a, &b);
64             g[a][b] = true;
65         }
66         bool flag = true;
67         for(int i = 1; i <= n; i ++)
68         {
69             flag = bfs(i);
70             if(!flag)
71                 break;
72         }
73         if(!flag)
74             puts("No");
75         else
76         {
77             int ans = 0;
78             for(int i = 1; i <= n; i ++)
79             {
80                 memset(vis, false, sizeof vis);
81                 ans += find(i);
82             }
83             printf("%d\n", ans);
84         }
85     }
86     return 0;
87 }