二分图匹配——匈牙利算法

题目链接:

P3386 【模板】二分图匹配

什么是二分图?

二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)是一个无向图,如果顶点V可分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B),则称图G为一个二分图。
——百度百科

20190921141059284.png

通俗地说,二分图就是一种特殊的无向图,它有两堆顶点。每一堆里的每一个顶点都只能和另一堆的顶点相连,而不能和自己这堆的其它点相连。上图就是一个二分图

如果我们删去一些边,使得任意两条边都不依附于同一个顶点,则称这种情况为匹配。最大匹配就是让剩余边的数字的数目最大。
特别的,如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配。

题解-匈牙利算法

交替路和增广路: 如下图,如果已匹配和待匹配的边(下图中黑线代表已匹配的边,红线代表未匹配的边)交替出现,则称这条路为交替路,交替路分为两种,一种是首尾边已匹配的,另一种是首尾边未匹配的。对于后者,它就是所谓的增广路了。在图中,红色的线路就是一条增广路。

20190921141353497.png

对于一条增广路,只要将它做取反操作,就能得到另一条交替路,而且这条交替路的匹配数比原来的增广路大一。我们一只重复这个找增广路->取反的操作,就能得到最大匹配了。
比如在上图中,如果我们匹配了( $U_2$ , $V_1$ ),( $U_3$ , $V_2$ )此时匹配数为2,发现( $U_3$ , $V_3$ )也能匹配,于是我们把 $U_3$ 的匹配改为 $V_3$ ,这样 $U_2$ 与 $V_2$ 匹配, $U_1$ 与 $V_1$ 匹配,发现匹配数就变成了3。
这就是匈牙利算法的全部内容了,其实还是很简单的

code:

#include <bits/stdc++.h>
using namespace std;
bool vis[1010],linked[1010][1010];
int next[1010];
int n,m,e;
bool dfs(int x){
    for(int i=1;i<=m;i++){
        if(!vis[i]&&linked[x][i]){
            vis[i]=true;
            if(!next[i]||dfs(next[i])){
                next[i]=x;
                return true;
            }
        }
    }
    return false;
}

int main(){
    
    cin>>n>>m>>e;
    int u,v;
    for(int i=1;i<=e;i++){
        cin>>u>>v;
        if(u<=n&&v<=m)
        linked[u][v]=true;
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        memset(vis,false,sizeof(vis));
        if(dfs(i)) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

原文链接:https://blog.csdn.net/WjNaG/article/details/101106395

本文链接:https://kaispace.com.cn/index.php/archives/543/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者