二分图：设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。

二分图匹配：给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

可以用匈牙利算法（Hungary Algorithm）解决

几个概念：

• 交替路（也叫交错路）：从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边……形成的路径叫交替路。
• 增广路：从一个未匹配点出发，走交替路，以另一个未匹配点为结尾（出发的点不算），则这条交替路称为增广路（Agumenting Path）。
• 增广路定理：任意一个非最大匹配的匹配一定存在增广路。

匈牙利算法的流程就是不断递归找增广路。设二分图的两个点集为A,B

对于A中的每个点，枚举从这个点连向B的所有边。

对于x1->y1，若y1当前没有匹配，或y1已经匹配了x2，但x2可以递归匹配另一个y2（ !cp[i] || find(cp[i]) ），则匹配成功，否则失败。

bool find(int x) {    for(int i = 1; i <= m; i++)        if(to[x][i] && !vis[i]) {            vis[i] = 1;            if(!cp[i] || find(cp[i])) {                cp[i] = x;                return 1;            }        }    return 0;}

 

注意这里的vis[]，如果没有可能会出现死循环的情况。每次匹配需要把vis[]清零。

完整代码如下

#include
      
       #include
       
        #define MogeKo qwqusing namespace std;const int maxn = 1005;bool to[maxn][maxn],vis[maxn];int n,m,e,u,v,ans,cp[maxn];bool find(int x) {    for(int i = 1; i <= m; i++)        if(to[x][i] && !vis[i]) {            vis[i] = 1;            if(!cp[i] || find(cp[i])) {                cp[i] = x;                return 1;            }        }    return 0;}int main() {    scanf("%d%d%d",&n,&m,&e);    for(int i = 1; i <= e; i++) {        scanf("%d%d",&u,&v);        if(u>n || v>m)continue;        to[u][v] = true;    }    for(int i = 1; i <= n; i++) {        memset(vis,0,sizeof(vis));        if(find(i))ans++;    }    printf("%d",ans);    return 0;}