P3386 【模板】二分图最大匹配题解

· · 题解

图的最大匹配问题

从一个图中选出一些边，使得任意两个边之间没有公共顶点。

一般图的最大匹配问题是 NP 完全的，但是对于二分图，可以使用匈牙利算法在 O(nm) 的时间复杂度内解决。

匈牙利算法

前置知识

二分图

可以将其中的点分为两份，称为左部和右部，每一份中的点之间没有边直接相接。

一个图是否是二分图，取决于是否存在长度为奇数的环，若有则不是二分图。显然成立。

增广路

假设我们目前已经选出一些边，称为匹配边，匹配边的端点为匹配点。如果存在一个路径，形如“非匹配边——匹配边——非匹配边——\dots——非匹配边”，且两端均为非匹配点，那么称其为增广路。也就是首尾均为非匹配边，且匹配边与非匹配边交错出现。

容易发现，如果图中存在增广路，那么只需要将匹配边与非匹配边取反，便可将匹配边的数量加一。换言之，如果图中不存在增广路，那么就得到了二分图的最大匹配。

原理

匈牙利算法通过尝试寻找以每个点为起点的增广路来得到二分图最大匹配。

如下图的情况，蓝色的点和边为已经匹配的点和边。

此时我们已经跑完了前两个点，现在要寻找第三个点出发的增广路。

于是三号点从自己的边出发，发现对面的点已经被匹配了。但是三号点也要匹配啊，于是它选择了暴力抢过这一个点，给二号点脸都气绿了。如下图：

二号点越想越气，于是把气发在了一号点上。它沿着自己的另一条边，抢过了一号点的匹配点。这下轮到一号点绿了。如下图：

一号点也很气，但是它发现自己还有一条边连向一个非匹配点。多一事不如少一事，于是它选择了匹配另外一个点。如下图：

于是皆大欢喜，所有点都找到了自己的匹配点。什么？你问四号点？那就是另外一个故事循环了。

那么如果匹配失败是怎样的呢？我们假设一号点没有向下的那条边。如下图：

此时二号点来抢一号点的匹配点，一号点当然不乐意。它发现自己根本没有其他能匹配的点了，于是忍无可忍无须再忍！一号点直接赶走了二号点。二号点一看一号点居然如此硬气，于是幡然醒悟，也要捍卫自己原本的匹配点。于是它又向三号点夺回了自己的匹配点，于是一切又回到了一开始的情况。如下图：

实现

实现上述的代码只需要一个 dfs 即可。如下，代码有详细注释。

int bo[N];//此点对应的匹配点。
bool in[N];//此右点是否已经到访过。
bool dfs(int now){
    for(int i=h[now];i;i=lian[i].ne){//链式前向星
        int to=lian[i].to;
        if(in[to])continue;
        in[to]=1;//记录此右点已经到访过
        if(!bo[to]||dfs(bo[to])){
            //如果此点没有匹配点，那么直接与它匹配。
            //否则，让它的原配再取尝试找新的匹配点，如果成功则说明可以交换。
            bo[to]=now;
            return 1;//匹配成功
        }
    }
    return 0;//匹配失败
}
int ans;
int main(){
    for(int i=1;i<=n;i++){
        if(dfs(i))ans++,//匹配成功，增广路长度加1
        memset(in,0,sizeof(in));
    }
}

正确性证明

很多题解只证明了为什么最大匹配不存在增广路，但是这是显然的。还有很多干脆没有正确性证明。我觉得此算法最重要的是证明以所有点为起点找一遍增广路后，图中不存在增广路。以下是证明：

首先如果一个点是非匹配点，那么就说明在以他开头的 dfs 中，找到的所有已匹配点都是不能改变配偶的。那么就算接下来搜到了这些点，也照样不能使其改变。自然也就没有再找一遍的必要了。所以就不存在增广路了。

时间复杂度

最坏情况对于每个点都要搜索完整个图，时间复杂度显然的 O(nm)。

完整代码

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define ld long double
#define dd double
//char buf[1<<23],*p1=buf,*p2=buf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?EOF:*p1++)
inline ll read() {
    ll x = 0, f = 1;
    char ch;
    while (((ch = getchar()) < 48 || ch > 57) && ch != EOF)if (ch == '-')f = -1;
    if (ch == EOF)x = EOF;
    while (ch >= 48 && ch <= 57)x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}
char __sta[1009], __len;
inline void write(ll x, ll bo) {
    if (x < 0)putchar('-'), x = -x;
    do __sta[++__len] = x % 10 + 48, x /= 10;
    while (x);
    while (__len)putchar(__sta[__len--]);
    if (bo == 3)return;
    putchar(bo ? '\n' : ' ');
}
const ll N=5e4+9;
int n,m,e;
//链式前向星
struct LIAN{
    int to,ne;
}lian[N*2];
int h[N],lcnt;
inline void add(int u,int v){
    lian[++lcnt].ne=h[u],lian[lcnt].to=v,h[u]=lcnt;
}
//二分图匹配
int bo[N];
bool in[N];
bool dfs(int now){
//  in[now]=1;
    for(int i=h[now];i;i=lian[i].ne){
        int to=lian[i].to;
        if(in[to])continue;
        in[to]=1;
        if(!bo[to]||dfs(bo[to])){
            bo[now]=to;
            bo[to]=now;
            return 1;
        }
    }
    return 0;
}
int ans;
int main() {
    n=read(),m=read(),e=read();
    for(int i=1;i<=e;i++){
        int u=read(),v=read();
        v+=n;
        add(u,v),add(v,u);
    }
    for(int i=1;i<=n;i++){
        if(dfs(i))ans++,
        memset(in,0,sizeof(in));
    }
    write(ans,1);

    return 0;
}