首先，介绍一些概念：
二分图：二分图又称作二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集（A,B），并且图中的每条边（i,j）所关联的两个顶点i和j分别属于这两个不同的顶点集（i in A,j in B），则称图G为一个二分图。
匹配：给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，这称M是一个匹配。选择这样的边数最大的子集的问题称为图的最大匹配问题。如果一个匹配中，图的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。
例如，图 3、图 4 中红色的边就是图 2 的匹配。
最小点覆盖：选了一个点就相当于覆盖了以它为端点的所有边，你需要选择最少的点来覆盖所有的边
1。一个二分图中的最大匹配数等于这个图中的最小点覆盖数
König定理是一个二分图中很重要的定理，它的意思是，一个二分图中的最大匹配数等于这个图中的最小点覆盖数。
2。最小路径覆盖=最小路径覆盖＝｜G｜－最大匹配数
在一个N*N的有向图中，路径覆盖就是在图中找一些路经，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联；（如果把这些路径中的每条路径从它的起始点走到它的终点，那么恰好可以经过图中的每个顶点一次且仅一次）；如果不考虑图中存在回路，那么每条路径就是一个弱连通子集．
由上面可以得出：
1.一个单独的顶点是一条路径；
2.如果存在一路径p1,p2,......pk，其中p1 为起点，pk为终点，那么在覆盖图中，顶点p1,p2,......pk不再与其它的顶点之间存在有向边．
最小路径覆盖就是找出最小的路径条数，使之成为G的一个路径覆盖．
路径覆盖与二分图匹配的关系：最小路径覆盖＝｜N｜－最大匹配数；
3。二分图最大独立集=顶点数-二分图最大匹配
独立集：图中任意两个顶点都不相连的顶点集合。
求解二分图的最大匹配可以用最大流(Maximal Flow)或者匈牙利算法（Hungarian Algorithm)，这里要说的是匈牙利算法。
交替路：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边……形成的路径叫做交替路。
增广路：从一个未匹配点出发，走交替路，如过途径另一个未匹配点，则这条交替路称为增广路。
例如，图6为图5的一条增广路。
我们可以看出，通过增广路找到的非匹配边比匹配边多一条，我们只需要把其中的匹配边变成非匹配边，非匹配边变为匹配边，我们就可以得到一个更大的匹配，并且这样做并不会破坏匹配的性质。这正是寻找增广路的性质。
匈牙利算法正是通过不断的寻找增广路来增大匹配的数目，当找不到增广路的时候即达到最大匹配。
算法模板如下：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
int m,n,k; //二分图的X部有n个顶点，Y部有m个顶点，有k条边
int pre[105]; //pre[j]=i表示i,j之间有一条匹配边
bool a[105][105]; //a[i][j]表示i,j之间有边相连
bool f[105];
bool dfs(int x)
{
for (int i=1;i<m;i++)
{
if ((!a[x][i])||(f[i])) continue;
f[i]=1;
if ((pre[i]==-1)||(dfs(pre[i]))) //找到一个未匹配点
{
pre[i]=x;
return 1;
}
}
return 0;
}
void hungary() //匈牙利算法
{
int ans=0;
memset(pre,-1,sizeof(pre));
for (int i=1;i<n;i++)
{
memset(f,0,sizeof(f));
if (dfs(i)) ans++;
}
printf("%d\n",ans);
}
int main()
{
while (scanf("%d%%dd",&n,&m,&k)!=EOF)
{
memset(a,0,sizeof(a));
for (int i=0;i<k;i++)
{
int w,e;
scanf("%d%d",&w,&e);
a[w][e]=1;
}
hungary();
}
return 0;
}