简介

如果在当前匹配方案下再也找不到增广路，那么当前匹配就是最大匹配了。

流程

1. 从任意一个没有被配对的点\(x\)开始，从点\(x\)的边中任意选一条边。如果此时点\(i\)没有被配对那么配对成功，则找到了一条增广路。如果点\(i\)此时已经被配对了，那么可以尝试将点\(i\)与其他点配对。如果尝试成功，则找到一条增广路。这里用\(match\)来记录配对关系，即\(match_i=x\)。并且将配对数\(+1\)。这个过程我们用dfs来实现。

2. 如果配对失败，就从点\(x\)的边中重选一条边尝试。直到点\(x\)配对成功或尝试完x所有的边。

3. 接下来对没有配对的点一一进行配对，直到所有的点都尝试完毕找不到新的增广路。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m,e,ans,match[N];
bool a[N][N],vis[N];
bool dfs(int x) {
    for(int i=1; i<=m; i++) {
        if(!vis[i]&&a[x][i]) {
            vis[i]=1;
            if(!match[i]||dfs(match[i])) {
                match[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main() {
    scanf("%d %d %d",&n,&m,&e);
    for(int i=1,u,v; i<=e; i++) {
        scanf("%d %d",&u,&v),a[u][v]=1;
    }
    for (int i=1; i<=n; i++){
        ans+=dfs(i);
        memset(vis,0,sizeof(vis));
    }
    printf("%d",ans);
    return 0;
}

后记

由这里转载。

二分图匹配

原文：https://www.cnblogs.com/Sam2007/p/13363042.html