[图论] 最大匹配问题归纳

一、定义

即在一个二分图中，找到最大的匹配对数。每个点只能最多和另外一个点配对。

二、情景

为了方便理解，这里考虑一下最大匹配场景：

• 有一列男生1..n，还有一列女生女生n + 1..n + m。即结点分开存；
• 愿意配对的男女会有边相连；
• 要求出男女配对的最大匹配数目。

三、解析

有两种方法可以解决最大匹配问题：匈牙利算法、Hopcroft_karp算法。

• 匈牙利算法

  • 时间复杂度O(VE)
  • 优点是代码简单，不超时时优先使用

• Hopcroft_karp算法

  • 时间复杂度O(sqrt(V)*E)
  • 优先时更快，缺点是代码复杂，类似最大流
  • 其实该算法就是将匈牙利算法中的find部分通过bfs分段，一点点来找匹配而已。

四、匈牙利算法 模板

bool find(int u){
    for(int v : G[u]){
        if(vis[v]) continue; 
        vis[v] = 1;
        if(belong[v] == 0 || find(belong[v])){
        // 若对象名花无主 或 对象能重新找到npy, 则 可以匹配该对象 
            belong[v] = u, belong[u] = v;
            return 1;
        }
    }
    return 0;
} 

int maxMatch(){
    int res = 0;
    for(int i = 1; i <= n; i ++){  // 男生逐个去邀请追女生
        memset(vis, 0, sizeof(vis)); // vis用于标记对象点是否判断过, 每次都要清零
        if(find(i)) res ++;  // 找到一个心仪的女生了
    }
    return res;
} 

五、Hopcroft_karp算法 模板

/*
类似最大流算法 数组解释：
dist[i]: 层数标记
belong[i]: i 的对象
*/
bool bfs(){
    queue<int> queue;
    memset(dist, -1, sizeof(dist));
    fin_dist = INF; // dist为当前终点的层数标记
    for(int u = 1; u <= n; u ++) if(!belong[u]) que.push(u), dist[u] = 0; // 若干起点
    while(!que.empty()){
        int u = que.front();
        que.pop();
        if(dist[u] > fin_dist) break; // 到增广路终点层数的点都标记好了就跳出, 后面不再标记
        for(int v : G[u]){
            if(dist[v] == -1){  // 未被标记 
                dist[v] = dist[u] + 1;
                if(!belong[v]) fin_dist = dist[v]; // 找到增广路, 确定增广路终点层数
                else dist[belong[v]] = dist[v] + 1, que.push(belong[v]); // 继续bfs 
            }
        } 
    } 
    return dist != INF;
}

bool find(int u){
    if(dist[u] > fin_dist) return 0；
    for(int v : G[u]){
        if(vis[v] || dist[v] != dist[u] + 1) continue;
        //  询问过 ||  不是上下层关系    则跳过
        vis[v]  = 1;
        if(belong[v] == 0 || find(belong[v])){
            // 若对象名花无主 或 对象能重新找到npy, 则 可以匹配该对象 
            belong[v] = u, belong[u] = v;
            return 1;
        } 
    }
    return 0;
} 

int Hopcroft_karp(){
    int res = 0;
    while(bfs()){ // 搜索有无增广路 
        memset(vis, 0, sizeof(vis));
        for(int i = 1; i <= n; i ++)
            if(!belong[i] && find(i)) res ++; 
            // 若没有女朋友 && 能找到 
    }
    return res; 
}

全原创