Featured image of post 二分图最大匹配匈牙利算法

二分图最大匹配匈牙利算法

二分图最大匹配

前言:其实老早就学了,但是之前学的时候不透彻,稀里糊涂背背模板就过去了。果然,在最近一次原题检测上找到了我,然后就“暴毙”了。
我就意识到学算法不能这么学,要摸清楚规律、掌握证明方法、思考推论过程。
俗话说“温故而知新”,的确,我也在复习的过程中有了更透彻的理解。所以我决定写一篇笔记。
本文有很多地方直接搬用了一些参考资料,所以本篇笔记原创部分主要为对关键部分进行解释。

建议:草稿纸和笔永远是最好的工具。在看本文过程中,要仔细思考任何一部分,不要囫囵吞枣。

注:本篇文章是我这个小蒟蒻写的,真正的dalao请看个玩笑便好,不必争论对错(但是欢迎指出文章存在的小错误)。

二分图初步

建议:如果你已对此有些许了解,可以根据目录直接跳到二分图匹配部分

什么是二分图

参考资料是这样介绍的:

  • 二分图又称作二部图,是图论中的一种特殊模型。
  • 设 $G=(V, E)$ 是一个无向图。如果顶点集 $V$ 可分割为两个互不相交的子集 $X$ 和 $Y$,并且图中每条边连接的两个顶点一个在 $X$ 中,另一个在 $Y$ 中,则称图 $G$ 为二分图。

但其实可以简化成一张图去理解:

上图就是一个二分图。

二分图性质

参考资料:

  • 定理:当且仅当无向图 $G$ 的每一个回路的边数均是偶数时,$G$ 才是一个二分图。如果无回路,相当于任一回路的边数为 $0$,故也视为二分图。

二分图判定

参考资料这里写得太复杂了,简单的话描述一下:

  • 如果是一个连通图
    1. 从顶点 $1$ 开始宽度遍历整个图($BFS$)
    2. 对遍历到的点进行染色,只染黑、白两色
    3. 染色过程中做到相邻点的颜色不同
  • 如果不是一个连通图
    • 在每个连通块中作判定,判定方法与上面相似

如下图,可判定为一个二分图:

为了观察方便,这里用红、蓝两色代替了黑、白两色。

二分图匹配

什么是匹配

先看看参考资料怎么说:

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

图中加粗的边是数量为 $2$ 的匹配。

这里讲得很清楚,不过多赘述(下文当资料讲得很简单明了时,也不会再过多解释)。

什么是最大匹配

选择边数最大的子图称为图的最大匹配问题
如图加粗的边是一个最大匹配:

可以简单理解为使 $X$ 部的顶点和 $Y$ 部的顶点匹配尽可能多。

什么是增广路径

设 $M$ 为二分图 $G$ 已匹配边的集合,若 $P$ 是图 $G$ 中一条连通两个未匹配顶点的路径($P$ 的起点在 $X$ 部,终点在 $Y$ 部,反之亦可),并且属 $M$ 的边和不属 $M$ 的边(即已匹配和待匹配的边)在 $P$ 上交替出现,则称 $P$ 为相对于 $M$ 的一条增广路径。

增广路径是一条“交错轨”。也就是说, 它的第一条边是目前还没有参与匹配的,第二条边参与了匹配,第三条边没有……最后一条边没有参与匹配,并且起点和终点还没有被选择过,这样交错进行,显然 $P$ 有奇数条边。

为什么 $P$ 会有奇数条边呢?

根据定义,$P$ 路径的起点和终点不在同一个部,所以必然是奇数条边。

下面来根据这个图找一下增广路:

易得一条路径:

$$ x_4 \rightarrow y_3 \rightarrow x_2 \rightarrow y_1\rightarrow x_1\rightarrow y_2 $$

因为 $y_2$ 是 $Y$ 部中未匹配的点,所以此路径是增广路径。

其中 $\in M$ 的边有 $(x_2,y_3),(x_1,y_1)$,不属于匹配的边有 $(x_4,y_3),(x_2,y_1),(x_1,y_2)$。
可见不属于匹配的边要多一条

如果我们想让情况变成匹配边会多一条,那就思考一下“取反”操作,即将匹配边变为非匹配边,反之同理。
可得:

可以得到这样的匹配 $M’=((x_3,y_4),(x_4,y_3),(x_2,y_1),(x_1,y_2))$。

仔细思考,发现匹配仍然合法。交错轨也还存在。
可以证明,当不能再找到增广路时,就已经得到了一个最大匹配。

为什么?
假设还能再找到一条增广路,那经过取反操作必定可以多增加一条匹配边。那最大匹配是最终形态,必定不会再有一条增广路。

而这,就是匈牙利算法的思路。

增广路径性质

  • $P$ 的路径长度必定为奇数,第一条边和最后一条边都不属于 $M$,因为两个端点分属两个集合,且未匹配。
  • $P$ 经过取反操作可以得到一个更大的匹配 $M’$。
  • $M$ 为 $G$ 的最大匹配当且仅当不存在相对于 $M$ 的增广路径。

以上很好理解,根据定义可推出。

匈牙利算法

为什么要用匈牙利算法

匈牙利算法就是用增广路求最大匹配问题,由匈牙利数学家 Edmonds 于1965年提出。

匈牙利算法长什么样

  1. 置 $M$ 为空
  2. 找出一条增广路径 $P$,通过取反操作获得更大的匹配$M’$代替$M$
  3. 重复步骤2,直至再也找不出新增广路

怎么找增广路

第一个想法肯定是用 dfs
从 $X$ 部一个未匹配的顶点 $u$ 开始,找一个未访问的邻接点 $v$($v$ 一定是 $Y$ 部顶点)。
对于 $v$,分两种情况:

  • 如果 $v$ 未匹配,则已找到一条增广路。
  • 如果 $v$ 已匹配,设 $v$ 的匹配顶点为 $w$($w$ 一定属 $X$ 部)。此时边 $(w,v)$ 为匹配边,根据“取反”思想,要将 $(w,v)$ 改为未匹配,$(u,v)$ 改为匹配。怎样才能实现这一点?要看从 $w$ 为起点出发能不能找到一条增广路 $P’$。如果成功,那 $u\rightarrow v\rightarrow P’$ 就是以 $u$ 为起点的增广路径。

那么我们就成功地把匈牙利算法核心部分搞懂了,可以上代码了。

代码实现匈牙利算法

寻找增广路部分

code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
// cx[i]表示与X部i点匹配的Y部顶点编号,cy[i]表示与Y部i点匹配的X部顶点编号
bool dfs(ll x)
{
    for (auto y : v[x])
    {
        if (!vis[y])
        {
            vis[y] = 1;
            if (cy[y] == -1 || dfs(cy[y]))
            {
                cx[x] = y, cy[y] = x;
                return 1;
            }
        }
    }
    return 0;
}

匈牙利算法主函数

code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#define mem(a,b) memset(a,b,sizeof(a))
ll maxmatch()
{
    ll ans = 0;
    mem(cx, -1);
    mem(cy, -1);

    rp(i, 1, n)
    {
        if (cx[i] == -1)
        {
            mem(vis, 0);
            ans += dfs(i);
        }
    }
    return ans;
}

板题&后记

前几天原题检测,考了一些最大匹配的原题。复习时才发现有很多纰漏平时没注意到,所以写了这篇文章。

还是挺耗费精力的,因为这种知识和图片打交道比较多,制作图片和上传都挺麻烦的。

挂个板子吧。

[USACO4.2]完美的牛栏The Perfect Stall

这里挂两个代码,在连接$X$部与$Y$部方面有些不同,根据个人习惯取舍咯……
本人主要是按照题目意思及时变通,并没有什么常用的版本。

版本 1:用一个数组存下两种关系(个人较常用)

 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
58
59
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define rp(i, o, p) for (ll i = o; i <= p; ++i)
#define pr(i, o, p) for (ll i = o; i >= p; --i)
#define mem(a, b) memset(a, b, sizeof(a))

const ll MAXN = 1e4 + 5; // 这里要注意一下,不然会RE

ll n, m;
ll s[MAXN];
bool vis[MAXN];
ll c[MAXN];
ll sum, en[MAXN << 1], hed[MAXN], lst[MAXN << 1];

void add(ll x, ll y) {
    en[++sum] = y;
    lst[sum] = hed[x];
    hed[x] = sum;
}

bool dfs(ll x) {
    for (ll i = hed[x]; i; i = lst[i]) {
        ll y = en[i];
        if (!vis[y]) {
            vis[y] = 1;
            if (!c[y] || dfs(c[y])) {
                c[y] = x;
                return 1;
            }
        }
    }
    return 0;
}

ll maxmatch() {
    ll ans = 0;
    rp(i, 1, n) {
        mem(vis, 0);
        if (dfs(i))
            ++ans;
    }
    return ans;
}

int main() {
    scanf("%lld%lld", &n, &m);
    rp(i, 1, n) {
        scanf("%lld", &s[i]);
        rp(j, 1, s[i]) {
            ll t;
            scanf("%lld", &t);
            add(i, t);
        }
    }
    printf("%lld\n", maxmatch());
    return 0;
}

版本 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
58
59
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define rp(i, o, p) for (ll i = o; i <= p; ++i)
#define pr(i, o, p) for (ll i = o; i >= p; --i)
#define pb push_back
#define mem(a, b) memset(a, b, sizeof(a))

const ll MAXN = 200 + 5;

ll n, m;
vector<ll> v[MAXN << 1];
ll cx[MAXN], cy[MAXN << 1];
bool vis[MAXN << 1];

bool dfs(ll x) {
    for (auto y : v[x]) {
        if (!vis[y]) {
            vis[y] = 1;
            if (cy[y] == -1 || dfs(cy[y])) {
                cx[x] = y, cy[y] = x;
                return 1;
            }
        }
    }
    return 0;
}

ll maxmatch() {
    ll ans = 0;
    mem(cx, -1);
    mem(cy, -1);

    rp(i, 1, n) {
        if (cx[i] == -1) {
            mem(vis, 0);
            ans += dfs(i);
        }
    }
    return ans;
}

int main() {
    scanf("%lld%lld", &n, &m);
    rp(i, 1, n) {
        ll x;
        scanf("%lld", &x);
        rp(j, 1, x) {
            ll y;
            scanf("%lld", &y);
            v[i].pb(y + n), v[y + n].pb(i);
        }
    }

    printf("%lld\n", maxmatch());

    return 0;
}