二分图最大匹配

发布于 2018-01-07  535 次阅读


二分图定义

二分图是图论中的一种特殊模型,是图论中的一种特殊的模型。我们设$ G(V,E) $是一个无向图,如果顶点$ V $能被分割为两个互不相交的子集,并且图中的每条边$ (i,j) $所关联的两个顶点$ i $和$ j $分别属于这两个不同的顶点集,则称图$ G $为一个二分图。
我们要实现的是求二分图的最大匹配。

算法实现

首先从任意一个未被配对的点u开始,从点u的边中找出一条边开始配对(设这条边是u->v)。如果点v没有被配对,则配对成功,找到了一条增广路。如果点v已经被配对了,就要尝试去移动原来与v配对的点,如果成功,更新原来的配对关系,配对树加一。如果失败,换一条边。
我们用match记录配对关系,如果u与v配对,则计作 $ match[v] = u $和 $ match[u] = v $
重复上述步骤直到找不出新的增广路为止。

代码实现

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN = 1000 + 5;

bool f[MAXN][MAXN];
bool used[MAXN];
int match[MAXN];
int n,m,e;

bool dfs(int x){
    for(int i = 1;i <= n;i++){
        if(!used[i] && f[x][i]){
            used[i] = true;
            if(!match[i] || dfs(match[i])){
                match[i] = x;
            return true;
            }
        }
    }
    return false;
}

int main(){
    scanf("%d%d%d",&n,&m,&e);
    for(int i = 1;i <= e;i++){
        int x,y;scanf("%d%d",&x,&y);
        if(x <= n && y <= m) f[x][y] = true;
    }
    int ans = 0;
    for(int i = 1;i <= n;i++){
        memset(used,false,sizeof(used));
        if(dfs(i)) ans++;
    }
    printf("%d\n",ans);
    return 0;
}

一个OIer。