理论基础
Berge 定理：图 G 的匹配 M 是最大匹配的充要条件是 G 中不存在 M 可扩展路。
Hall 定理：设 G 是具有二划分 (X, Y) 的二部图，则 G 有饱和 X 的匹配当且仅当对 $\forall S \subseteq X, |N(S)|\ge |S|$，其中 N(S) 表示 S 的所有邻点之集。
算法步骤
输入：二部图 G=(X, Y).
输出：G 的一个最大匹配 M .
第0步：任取图 G 的一个匹配 M 设 X 中 M 非饱和点的集合为 A.
第1步：若$A=\phi$，则停止，输出当前的 M；否则，任取$x\in A$，记 S := {x}，T := $\phi$，转到下一步.
第2步：若$N(S)\subseteq T$，则不存在从 x 出发的 M 增广路，令 A := A - {x}，转第一步；否则，取$y\in N(S)-T$ 转下步.
第3步：若y是 M 饱和的，设 $yz\in M$，令 $S := S\bigcup {z}$，$T := T\bigcup {y}$，转第1步；否则获得一条 M 增广路 P(x, y)，令 M := M$\oplus$E(P)， A := A - {x, y}，转第一步.
参考代码
1 const int MAXN = 1000;
2 int uN, vN; // u, v数目，要初始化！！！
3 bool g[MAXN][MAXN]; // g[i][j] 表示xi与yj相连
4 int xM[MAXN], yM[MAXN]; // 输出量
5 bool chk[MAXN]; // 辅助量检查某轮y[v]是否被check
6 bool SearchPath(int u){
7 int v;
8 for(v = 0; v < vN; v++)
9 if(g[u][v] && !chk[v])
10 {
11 chk[v] = true;
12 if(yM[v] == -1 || SearchPath(yM[v]))
13 {
14 yM[v] = u; xM[u] = v;
15 return true ;
16 }
17 }
18 return false ;
19 }
20 int hungary(){
21 int u, ret = 0 ;
22 memset(xM, -1, sizeof (xM));
23 memset(yM, -1, sizeof (yM));
24 for(u = 0; u < uN; u++)
25 if(xM[u] == -1){
26 memset(chk, false, sizeof (chk));
27 if(SearchPath(u)) ret++;
28 }
29 return ret;
30 }