二分图最大匹配

给定一张二分图，有 nn 个点，mm 条边。求最大匹配。

可以使用匈牙利算法求解，复杂度 O(nm)O(nm)。

如果使用 dinic 算法，可以做到复杂度为 O(nm)O(n\sqrt{m})

dinic 算法详见 网络流初步-最大流算法。
具体来说，建立超级源点和超级汇点，然后建容量为 1 的边，跑最大流即为最大匹配。

匈牙利算法的本质就是找增广路，基于贪心思想。我们来看一个例子。

首先考虑给节点 1 寻找匹配。发现可以匹配右边的节点 1，则成功匹配。

然后考虑给节点 2 寻找匹配。发现能匹配的唯一一个节点 1 已经被占用，尝试让左边的节点 1 换一个匹配，即等价于找一个增广路。

这样就找到了这张图的最大匹配（3）。我们接下来考虑写一个递归函数实现这种协商找增广路的算法。

匈牙利算法

我们定义一个递归函数 bool dfs(int u)，代表为节点 u 寻找匹配。
数组 int match[v] 表示右部图中节点 v 已经匹配上的左部图节点。
数组 bool used[v] 表示右部图中节点 v 是否已经在本轮中访问过。

则可以写出如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
vector<int> G[N];

int match[N];
bool used[N];

bool dfs(int u){
    for(int v:G[u]){
        if(used[v])continue;
        used[v]=1;
        if(match[v]==0 || dfs(match[v])){
            match[v]=u;
            return 1;
        }
    }
    return 0;
}

int solve(){
    int ans;
    for(int i=1;i<=n;i++){
        memset(used,0,sizeof(used));
        ans+=dfs(i);
    }
    return ans;
}

若 dfs(u) 返回 1，则代表成功为当前节点找到了一个匹配。

重点在第 10 行中 if 语句的条件：

  1. match[v]==0，代表当前节点 v 还没有人跟他匹配，这样直接让 u 跟 v 匹配。
  2. dfs(match[v])，代表可以让 v 的原配和其他人匹配，这样也可以让 u 跟 v 匹配。

还要注意 used 数组。我们不会需要让一个右部节点 v 协商两次（因为如果第一次协商失败了，第二次一定失败）。used 数组需要在主程序中每次清零。因为是在找一条增广路的过程中不需要重复访问，两次不同的增广路需要清零。

模板

洛谷P3386 【模板】二分图最大匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
using namespace std;

const int N = 1000;

vector<int> G[N];

bool used[N];
int match[N];

bool dfs(int u){
    for(int v:G[u]){
        if(used[v])continue;
        used[v]=1;
        if(match[v]==0 || dfs(match[v])){
            match[v]=u;
            return 1;
        }
    }
    return 0;
}

int main(){
    int n,m,t;
    scanf("%d%d%d",&n,&m,&t);
    while(t--){
        int u,v;scanf("%d%d",&u,&v);
        G[u].push_back(v);
    }

    int ans = 0;
    for(int i=1;i<=n;i++){
        memset(used,0,sizeof(used));
        ans += dfs(i);
    }
    printf("%d\n",ans);
    return 0;
}