二分图匹配-HK算法

先把代码贴上，其他南京回来再补了。。

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <iostream>

 #include <ctime>

 #include <vector>

 #include <list>

 #include <queue>

 #define M0(a) memset(a, 0, sizeof(a))

 #define Inf 0x7fffffff

 #define MXN 2110

 using namespace std;

 vector<int> edge[MXN];

 int dx[MXN], dy[MXN];

 int a[][];

 bool state[];

 int match[], Mx[];

 int n, m;

 void add(int x, int y){

     edge[x].push_back(y);

     edge[y].push_back(x);

 }

 void init(){

     M0(a);

     int x, y;

     for (int i = ; i <= n + m; ++i)

         edge[i].clear();

     for (int i = ; i <= n; ++i){

          scanf("%d%d", &x, &y);

          a[x][y] = i;

          a[x + ][y] = i;

     }

     for (int i = ; i <= m; ++i){

          scanf("%d%d", &x, &y);

          int now = a[x][y];

          if (now) add(i + n, now);

          now = a[x][y + ];

          if (now) add(i + n, now);

     }

 }

 bool bfs(){

     queue<int> q;

     bool flag = false;

     M0(dx);

     M0(dy);

     for (int i = ; i <= n; ++i)

        if (!Mx[i]){

             q.push(i);

             dx[i] = ;

        }

     int u, v;

     while (!q.empty()){

         u = q.front();

         for (int i = ; i < edge[u].size(); ++i){

              v = edge[u][i];

              if (dy[v]) continue;

              dy[v] = dx[u] + ;

              if (match[v] == -) flag = true;

              else {

                      q.push(match[v]);

                      dx[match[v]] = dy[v] + ;

                   }

         }

         q.pop();

     }

     return flag;

 }

 bool search_path(int u){

      int v;

      for (int i = ; i < edge[u].size(); ++i){

          v = edge[u][i];

          if (dy[v] != dx[u] + ) continue;

          if (!state[v]){

               state[v] = true;

               if (match[v] == - || search_path(match[v])){

                   Mx[u] = v;

                   match[v] = u;

                   return true;

               }

          }

      }

      return false;

 }

 void HK(){

     M0(Mx);

     int M = ;

     memset(match, -, sizeof(match));

     while (bfs()){

        M0(state);

        for (int i = ; i <= n; ++i)

           if(!Mx[i] && search_path(i)) ++M;

     }

     printf("%d\n", n + m - M);

 }

 int main(){

   //   freopen("hdu4619.in","r", stdin);

   //   freopen("hdu4619.out","w", stdout);

      while (scanf("%d%d", &n, &m) != EOF){

          if (!n) break;

          init();

          HK();

      }

   //   fclose(stdin); fclose(stdout);

 }