学步园

#include<stdio.h>
#include<string.h>
const int max=510;
int map[max][max];
int flag[max],mat[max],k,n,m;
int find(int i)
{
	for(int j=1;j<=m;j++)
		if(!flag[j]&&map[i][j])
		{
			flag[j]=1;
	       if(mat[j]==-1||find(mat[j]))
		   {
			   mat[j]=i;
		       return 1;
		   }
		}
		return 0;
}
int matchpeople(int n,int m)
{
	int match=0;
	memset(mat,-1,sizeof(mat));
	for(int i=1;i<=n;i++)
	{
		memset(flag,0,sizeof(flag));
		match+=find(i);
	}
	return match;
}
int main()
{
	int i,girl,boy;
	while(scanf("%d",&k)&&k)
	{
		scanf("%d%d",&n,&m);
		memset(map,0,sizeof(map));
		for(i=0;i<k;i++)
		{
			scanf("%d%d",&girl,&boy);
			map[girl][boy]=1;
		}
		printf("%d\n",matchpeople(n,m));
	}
	return 0;
}

邻接表的形式：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
using namespace std;
 
const int NV = 1005;
const int NE = 3000;
 
struct MaxMatch {
    int n, size;
    int head[NV];
    int aug[NV];
    bool mark[NV];
 
    struct Edge {
        int v, w, next;
        Edge () {}
        Edge (int V, int NEXT, int W = 0) : v(V), next(NEXT), w(W) {}
    }E[NE];
 
    inline void init(int vx) {
        n = vx, size = 0;
        for (int i = 0; i <= n; i++) {
            head[i] = -1;
        }
    }
 
    inline void insert(int u, int v, int w = 0) {
        E[size] = Edge(v, head[u], w);
        head[u] = size++;
    }
 
    inline int Hungary(int n) {
        int match = 0;
        memset(aug, -1, sizeof(aug));
        for (int i = 1; i <= n; i++) {
            if (aug[i] == -1) {//剪枝
                memset(mark, false, sizeof(mark));
                match += Find(i);
            }
        }
        return match;
    }//Hungray
 
    inline bool Find(int u) {
        for (int i = head[u]; i != -1; i = E[i].next) {
            int v = E[i].v;
            if (mark[v]) continue;
            mark[v] = true;
            if (aug[v] == -1 || Find(aug[v])) {
                aug[v] = u, aug[u] = v;
                return true;
            }
        }
        return false;
    }//Find
}G;
 
int main() {
       int k, m, n, a, b;
       while (~scanf("%d", &k), k) {
           scanf("%d%d", &m, &n);
           G.init(m + n);
           while (k--) {
               scanf("%d%d", &a, &b);
               G.insert(a, b + m);
         }//while(k--)
         printf("%d\n", G.Hungary(m));
      }//while
   return 0;
}

网上容易理解的详细描述：

#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;

const int N = 505;

bool map[N][N], flag[N];
int pre[N];
int n, m, num;

//匈牙利算法（二分匹配）
int find(int cur)   //cur为当前女生
{
    int i;
    for(i = 1; i <= m; i++) //被匹配的男生
    {
        if(map[cur][i] && !flag[i]) //该男生未被匹配
        {
            flag[i] = true; //这次匹配中，标记该男生已匹配
            if(pre[i] == -1 || find(pre[i]))    //该男生没有女生 or 该女生继续找其他男生 -> ok
            {
                pre[i] = cur;   //男生[i]属于女生cur
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    int i, girl, boy, sum;
    while(scanf("%d", &num), num)
    {
        scanf("%d %d", &n, &m);     //n是女生数量，m是男生数量
        memset(map, false, sizeof(map));
        memset(pre, -1, sizeof(pre));
        for(i = 0; i < num; i++)
        {
            scanf("%d %d", &girl, &boy);
            map[girl][boy] = true;  //可以匹配
        }
        sum = 0;
        for(i = 1; i <= n; i++)     //女生去匹配男生
        {
             memset(flag, 0, sizeof(flag)); //每次重新标记0
             sum += find(i);
        }
        printf("%d\n", sum);
    }

    return 0;
}

匈牙利二分匹配主要是增广路的查找，逐个逐个匹配，若那个人被匹配了，则找匹配那个的人看看能不能找其他人匹配，不断地找，