二分图匹配

简介

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

流程

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;
}

后记

由这里转载。