hdu 2444 The Accomodation of Students (判断二分图，最大匹配)

  1 #include <map>
  2 #include <queue>
  3 #include <cmath>
  4 #include <vector>
  5 #include <string>
  6 #include <cstdio>
  7 #include <cstring>
  8 #include <climits>
  9 #include <iostream>
 10 #include <algorithm>
 11 #define INF 0xffffff
 12 using namespace std;
 13 const int my_max = 205;
 14 
 15 int nn, mm, n, m, a, b, my_line[my_max][my_max], my_G[my_max][my_max],
 16     my_left[my_max], my_right[my_max], my_color[my_max], my_book[my_max];
 17 
 18 bool my_dfs(int x)
 19 {
 20     for (int i = 1; i <= n; ++ i)
 21     {
 22         if(my_color[i] == 1 && !my_book[i] && my_G[x][i])
 23         {
 24             my_book[i] = 1;
 25             if (!my_right[i] || my_dfs(my_right[i]))
 26             {
 27                 my_right[i] = x;
 28                 return true;
 29             }
 30         }
 31     }
 32     return false;
 33 }
 34 
 35 bool my_bfs(int x)
 36 {
 37     queue <int> Q;
 38     Q.push(x);
 39     my_color[x] = 1;
 40 
 41     while (!Q.empty())
 42     {
 43         int my_now = Q.front();
 44         for (int i = 1; i <= n; ++ i)
 45         {
 46             if (my_G[my_now][i])
 47             {
 48                 if (my_color[i] == -1)
 49                 {
 50                     Q.push(i);
 51                     my_color[i] = !my_color[my_now];
 52                 }
 53 
 54                 else if (my_color[my_now] == my_color[i])
 55                     return true;
 56             }
 57         }
 58         Q.pop();
 59     }
 60 
 61     return false;
 62 }
 63 
 64 int my_hungarian()
 65 {
 66     int my_ans = 0;
 67 
 68     for (int i = 1; i <= n; ++ i)
 69     {
 70         memset(my_book, 0, sizeof(my_book));
 71         if (my_color[i] == 0 && my_dfs(i))
 72             my_ans ++;
 73     }
 74     return my_ans;
 75 }
 76 
 77 int main()
 78 {
 79     while (~scanf("%d%d", &n, &m))
 80     {
 81         memset(my_line, 0, sizeof(my_line));
 82         memset(my_right, 0, sizeof(my_right));
 83         memset(my_color, -1, sizeof(my_color));
 84         memset(my_G, 0, sizeof(my_G));
 85 
 86         while (m --)
 87         {
 88             scanf("%d%d", &a, &b);
 89             my_G[a][b] = my_G[b][a] = 1;
 90         }
 91 
 92         bool flag_is_bipG = true;
 93         for (int i = 1; i <= n; ++ i)
 94             if (my_color[i] == -1 && my_bfs(i))
 95             {
 96                 flag_is_bipG = false;
 97                 printf("No\n");
 98                 break;
 99             }
100         if (!flag_is_bipG) continue;
101 
102         printf("%d\n", my_hungarian());
103     }
104     return 0;
105 }