匈牙利算法（增广路） 二分图最大匹配

· · 个人记录

每个点都可以和相邻点配对，每个配对只能有两个点，如果没有临边，或者有矛盾，例如多个点都连着一个点，也可以单着。最终配对的对数叫做匹配数，求最大匹配就是使匹配数最大。

匈牙利算法求最大匹配是基于增广路定理的：一条从非匹配边的一个端点出发，到另一个非匹配边端点结束，匹配边和非匹配边交替出现的路径称为增广路，由于出发点和结束点都是非匹配边的端点，这条路径上的非匹配边个数一定为偶数，且比匹配边多1.于是沿着增广路，把所有匹配边都变成非匹配边，非匹配边都变成匹配边，这条路径上的匹配边个数会增加1，这个过程称为增广，这个定理称为增广路定理。

匈牙利算法的过程就是：从任意一点出发，如果相邻点也未配对，则配对，如果相邻点已配对，沿着相邻点方向寻找增广路，并进行增广。直到不存在增广路为止，此时匹配数达到最大。

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
#define ll long long 
#define db double
#define inf 0x3f3f3f3f
#define rep(i,x,y) for(int i=(x);i<=(y);i++)
#define pll pair<int,int>
int n,m,k,ans,cnt,cp[N],head[N];//cp保存与该店配对的点编号
bool vis[N];
int read(void)
{
    int x=0,f=1;char s;
    s=getchar();
    while(s>'9'||s<'0'){
        if(s=='-')f=-1;
        s=getchar(); 
    }
    while(s<='9'&&s>='0'){
        x=x*10+s-'0';
        s=getchar(); 
    }
    x*=f;
    return x;
}
struct EDGE{
    int v,w,next;
}e[N*100];
void add(int u,int v,int w=0){
    e[++cnt]=(EDGE){v,w,head[u]};
    head[u]=cnt; 
}
bool dfs(int now){
    for(int i=head[now];i;i=e[i].next){
        if(!vis[e[i].v]){
            vis[e[i].v]=1;//不走回头路
            if(!cp[e[i].v]||dfs(cp[e[i].v])){
                    //如果未配对，就配对
                //如果已配对，就看该点的配对点能否找到另一个点配对
                    //这个递归过程实际上就是增广
                cp[e[i].v]=now;
                return 1;//如果完成增广，返回成功
            }
        }
    }
    return 0;//没有可以增广的路径，返回失败
}
int main(){
    n=read(),m=read(),k=read();
    rep(i,1,k){
        int x,y;
        x=read(),y=read();
        add(x,n+y);//这个算法实际上只会出现左部点出发寻找相邻点的过程
            //因此只用左部点向右部点建边
    }
    rep(i,1,n){//增广也只用遍历左部点
        memset(vis,0,sizeof(vis));
        ans+=dfs(i);//如果增广成功，边数加1
    }
    cout<<ans;
}

以上理解其实是把递归拆开看的，比较麻烦，还有一种不拆递归，比较容易理解的思路：按序号遍历所有左部点，如果该点的相邻点存在未配对的，就配对，如果相邻点已配对，就看相邻点的配对点能否找到另一个点配对，如果能，就让配对点去找那个点配对，相邻点和自己配对。这样思考就只限于一层了，不用把递归打开。