搜索与图论 - 匈牙利算法

2020-09-25 09:45:32

匈牙利算法讲的是二分图的最大匹配数。时间复杂度最坏$O(nm)$， 实际上远小于$O(nm)$。给定一个二分图，然后找到最大的匹配对数(数据不能重复使用)。

匈牙利算法也是基于贪心的一个算法。属于不到南墙终不回。算法基本流程：

  • 为每个i找一个j，如果存在关系，并且j没有匹配，就让他两匹配
  • 如果j已经匹配了，就找j匹配的对象，让其是否能换一个，如果可以行就匹配成功。不可行就匹配不成功

AcWing 861. 二分图的最大匹配

来源: https://www.acwing.com/problem/content/description/863/

给定一个二分图，其中左半部包含n1个点（编号1-n1），右半部包含n2个点（编号1-n2），二分图共包含m条边。

数据保证任意一条边的两个端点都不可能在同一部分中。

请你求出二分图的最大匹配数。

二分图的匹配：给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。

输入格式
第一行包含三个整数 n1、 n2 和 m。

接下来m行，每行包含两个整数u和v，表示左半部点集中的点u和右半部点集中的点v之间存在一条边。

输出格式
输出一个整数，表示二分图的最大匹配数。

数据范围
$1≤n1,n2≤500,$
$1≤u≤n1,$
$1≤v≤n2,$
$1≤m≤10^5$
输入样例：

1
2
3
4
5
2 2 4
1 1
1 2
2 1
2 2

输出样例：

1
2
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <cstring>

using namespace std;
const int N = 510, M = 100010;
int h[N], e[M], ne[M], idx;
int n1, n2, m;
int match[N];
bool st[N];

bool find(int x)
{
    for(int i = h[x]; i != -1; i = ne[i])
    {
        int j = e[i];
        // 如果st没有遍历过
        if (!st[j])
        {
            st[j] = true;
            // 如果j没有匹配或者能够找到j的匹配者换一个进行匹配
            if (match[j] == 0 || find(match[j]))
            {
                match[j] = x;
                return true;
            }
        }
    }
    return false;
}


void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

int main()
{
    cin >> n1 >> n2 >> m;
    memset(h, -1, sizeof h);
    while(m--)
    {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    int res = 0;
    for(int i = 1; i <= n1; i++)
    {
        memset(st, false, sizeof st);
        if (find(i)) res++;
    }

    cout << res << endl;
    return 0;
}
  1. 1. AcWing 861. 二分图的最大匹配