二分图匹配-HK算法

先把代码贴上，其他南京回来再补了。。
  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <algorithm>
  6 #include <iostream>
  7 #include <ctime>
  8 #include <vector>
  9 #include <list>
 10 #include <queue>
 11 #define M0(a) memset(a, 0, sizeof(a))
 12 #define Inf 0x7fffffff
 13 #define MXN 2110
 14 using namespace std;
 15 vector<int> edge[MXN];
 16 int dx[MXN], dy[MXN];
 17 int a[120][120];
 18 bool state[2010];
 19 int match[2010], Mx[2010];
 20 int n, m;
 21 
 22 void add(int x, int y){
 23     edge[x].push_back(y);
 24     edge[y].push_back(x); 
 25 }
 26 
 27 void init(){
 28     M0(a);
 29     int x, y;
 30     for (int i = 0; i <= n + m; ++i)
 31         edge[i].clear();
 32     for (int i = 1; i <= n; ++i){
 33          scanf("%d%d", &x, &y);
 34          a[x][y] = i;
 35          a[x + 1][y] = i;
 36     }
 37     for (int i = 1; i <= m; ++i){
 38          scanf("%d%d", &x, &y);
 39          int now = a[x][y];
 40          if (now) add(i + n, now);
 41          now = a[x][y + 1];
 42          if (now) add(i + n, now);
 43     }
 44 }
 45 
 46 bool bfs(){
 47     queue<int> q;
 48     bool flag = false;
 49     M0(dx);
 50     M0(dy);
 51     for (int i = 1; i <= n; ++i)
 52        if (!Mx[i]){
 53             q.push(i);
 54             dx[i] = 1;        
 55        } 
 56     int u, v;
 57     while (!q.empty()){
 58         u = q.front();
 59         for (int i = 0; i < edge[u].size(); ++i){
 60              v = edge[u][i];
 61              if (dy[v]) continue;
 62              dy[v] = dx[u] + 1;
 63              if (match[v] == -1) flag = true;
 64              else {
 65                      q.push(match[v]);
 66                      dx[match[v]] = dy[v] + 1;
 67                   }
 68         } 
 69         q.pop();  
 70     }
 71     return flag;
 72 }
 73 
 74 bool search_path(int u){
 75      int v;
 76      for (int i = 0; i < edge[u].size(); ++i){
 77          v = edge[u][i];
 78          if (dy[v] != dx[u] + 1) continue;
 79          if (!state[v]){
 80               state[v] = true;
 81               if (match[v] == -1 || search_path(match[v])){
 82                   Mx[u] = v;
 83                   match[v] = u;
 84                   return true;             
 85               }             
 86          }
 87      }
 88      return false;
 89 }
 90 
 91 void HK(){
 92     M0(Mx);
 93     int M = 0;
 94     memset(match, -1, sizeof(match));
 95     while (bfs()){
 96        M0(state);
 97        for (int i = 1; i <= n; ++i)
 98           if(!Mx[i] && search_path(i)) ++M;
 99     }
100     printf("%d
", n + m - M);
101 }
102 
103 int main(){
104   //   freopen("hdu4619.in","r", stdin);
105   //   freopen("hdu4619.out","w", stdout);    
106      while (scanf("%d%d", &n, &m) != EOF){
107          if (!n) break;
108          init();
109          HK();
110      }
111   //   fclose(stdin); fclose(stdout);
112 }