匈牙利算法，二分图带权匹配

[[ slider_text ]]

[[ item.c ]]

匈牙利算法，二分图带权匹配

发布时间 2025-01-22 作者：zhangminchen 来源：算法小站

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

## 匈牙利算法
算法主要过程，还是围绕**交错路**找匹配

1）一开始令$$S = \empty$$，所有边都是非匹配边
2）寻找增广路径`path`，把路径上所有边的匹配状态取反，得到一个更大的匹配$$S^{\prime}$$
3）重复上面步骤，直到不存在增广路

可以用`dfs`来找增广路，尝试给每一个左边的$$x \in X$$，找到一个右边的$$y \in Y$$，$$y$$能和$$x$$匹配
需要满足以下两个条件之一
1）$$y$$本身就是非浸润点，此时$$(x, y)$$是非匹配边，可以选进来
2）$$y$$已经和左边的$$x^{\prime}$$匹配了，从$$x^{\prime}$$出发，沿着交错路走，能找到另一个匹配点$$y^{\prime}$$
此时存在增广路$$x \to y \to x^{\prime} \to y^{\prime}$$，`dfs`回溯的时候，标记`match[y] = x`，具体见下图

> 实际上，dfs 回溯的过程，恰好完成了**增广路取反**操作，见下图所示
![](/media/content_img/KM-augment.png)

```bash
void solve() {
    vector<vector<int> > g(maxn);
    vector<int> vis, match(maxn, 0);

auto dfs = [&](auto &dfs, int x) -> bool {
        for (auto y : g[x]) {
            if (!vis[y]) {
                vis[y] = 1;
                if (!match[y] || dfs(match[y])) {
                    match[y] = x;
                    return true;
                }
            }
        }
        return false;
    };
	
	int res = 0;
	for (int i = 1; i <= n; i++) {
		vis.assign(maxn, 0);
		if (dfs(dfs, i)) res += 1;
	}
	
	res 返回最大匹配数量
}
```

不过一般二分图匹配，都是直接用 dinic 做，复杂度能优化到$$O(m\sqrt{n})$$

## 二分图带权匹配
考虑处理的图是完全图$$K\_{n, n}$$，如果不满足，可以插入缺少的边，并让其权值为`0`
我们处理的各个边都是非负权值的，所以有某个权值最大的匹配是完美匹配，考虑最大权匹配及其对偶问题

### 加权二分匹配及其对偶
**问题模型**
有$$n$$个农场生产玉米，$$n$$个加工厂，农产$$i$$生产的玉米，给加工厂$$j$$，产生利润$$w(i, j)$$
现在需要找到一个匹配，使得总利润最大

同时，政府希望少生产点玉米，如果农业公司不选择农场$$i$$，政府补贴$$u_i$$，如果不使用加工厂$$j$$，政府补贴$$v_j$$
政府支付的补贴，必须对所有$$i, j, \quad u_i + v_j \geqslant w(i, j)$$成立，同时希望有一个方案，使得$$\sum u_i + \sum v_j$$最小

**定义**
**最大权匹配**
一个$$n \times n$$矩阵的**截断**，每行每列各取一个元素得到的$$n$$个位置，找出和最大的一个截断，这就是**最大权匹配问题**
将非负权值$$w(i, j)$$分配给$$K\_{n, n}$$的边$$(x_i, y_j)$$，找出完美匹配$$M$$使得$$w(M)$$最大

**最小权覆盖**
给定所有边的权值，对标记$$\\{u_1, u_2, \cdots, u_n\\}, \\{v_1, v_2, \cdots, v_n\\}$$适当选择
使得$$u_i + v_j \geqslant w(i, j)$$对任意$$i, j$$均成立，覆盖$$(u, v)$$的代价$$c(u, v) = \sum u_i + \sum v_j$$
最小权覆盖，使得最小的一个覆盖

**最小权匹配**
很简单，选一个很大的$$M$$，然后权值调整成$$M-w(i, j)$$，求最大权匹配

### 对偶性
对于加权二分图$$G$$的一个完美匹配$$M$$和加权覆盖$$c(u, v)$$，有$$c(u, v) \geqslant w(M)$$
并且$$c(u, v) = w(M)$$当且仅当$$M$$是满足$$u_i + v_j = w(i, j)$$的边$$(x_i, y_i)$$组成的
简单来说，最大权匹配 = 最小权覆盖

> 证明
> 必要性，在$$M$$的每一条边上，对约束$$u_i + v_j \geqslant w(i, j)$$求和，就有$$c(u, v) \geqslant w(M)$$
充分性，$$c(u, v) \geqslant w(M)$$对任意匹配和覆盖都成立，$$c(u, v) = w(M)$$就表明最优了

## 匈牙利算法
**相等子图**
是$$G$$的生成子图，但是只包括满足$$l(x) + l(y) = w(x, y)$$的边$$(x, y)$$
其中$$l(x)$$是可行顶标，必须满足$$l(x) + l(y) \geqslant w(x, y)$$

![](/media/content_img/KM01.png)

**算法思路**
不难想到，任意构造一个可行顶标，比如$$Y$$的顶标是$$0$$，$$X$$的顶标取从它出发的所有边的最大权值
然后取相等子图的最大匹配
如果存在完美匹配，那么算法终止，否则修改顶标，使得相等子图的边变得更多，则有更大机会存在完美匹配

**怎么修改顶标呢？考虑一些性质**
1.$$(X-R, Y-T)$$是没有边的，否则可以继续增广，因为$$R$$已经是增广路径算法找到的，$$\in X$$的最大点覆盖了
另外，$$(R, T)$$的边均为非匹配边，因为$$R, T$$都是$$\in |Q|$$的点覆盖
因为`最小点覆盖 = 最大匹配`，点覆盖中的任意两个点，都是非匹配边

2.令$$S = X-R$$，在相等子图上执行增广路径算法，考虑**匹配边**$$(S, T) \leftarrow (X-R, T)$$
怎么修改顶标呢？首先要保证**原来的匹配边**$$(S, T)$$不会离开相等子图
可以考虑将$$S$$中所有点的顶标$$-\delta$$，同时$$T$$中所有点的顶标$$+\delta$$
这样，原来相等子图中没有$$(S, Y-T)$$的边，将$$S$$中的顶标减小一定的数$$\delta$$之后
就可能有$$(S, Y-T)$$的**新边加入相等子图**，不断调整顶标，使得相等子图中的边尽可能多

3.那么，接下来的问题主要就是，$$\delta$$应该取多少？
对于相等子图，必须保证$$l(x) + l(y) \geqslant w(x, y)$$恒成立

首先，原来的相等子图，$$(S, T): \quad l(x) + \delta, \ l(y) - \delta$$，其中$$l(x) + l(y)$$是不变的
仍然能够保证$$l(x) + l(y) \geqslant w(x, y)$$

现在考虑将新边$$x \in S, y \in Y-T$$加入相等子图，是否仍然保持恒成立？实际上
```math
\displaystyle
\begin{cases}
l'(x) = l(x) - \delta \\
l'(y) = l(y)
\end{cases}
```
那么我们需要$$l'(x) + l'(y) = l(x) - \delta + l(y) \geqslant w(x, y)$$恒成立
也就是说，我们要保证$$\delta \leqslant l(x) + l(y) - w(x, y)$$恒成立

我们取$$\delta = \min(l(x) + l(y) - w(x, y))$$即可

**匈牙利算法**
给$$T$$中的每个点$$y$$定义松弛量$$\text{slack}(y) = \min\\{l(x) + l(y) - w(x, y)\\}$$
在算法执行的时候，维护相等子图的$$(S, T)$$，迭代的时候考虑$$T'$$中的点
令$$\delta = \min \\{\text{slack}(y),  \quad y \in Y-T \\}$$，继续增广

### 算法实现
如果边$$(x, y)$$加入相等子图，那么有如下两种情况
情况一，如果$$y$$未浸润，那么找到增广路
情况二，如果$$y$$已经和$$S$$中的点$$yx(y)$$匹配，那么将$$yx(y), y$$分别加入$$S, T$$中

为了实现匈牙利算法，还需要定义一些东西
首先是，对于$$x \in S$$，枚举$$y \in Y$$中的每个节点
定义**松弛量**$$\text{slack}(y) = \min \\{lx(x) + ly(y) - w(x, y)\\}$$
实际松弛的时候，我们用`visy(y) = {1 or 0}`来标记$$y$$是在$$T$$集中，还是$$Y-T$$集中

根据之前的分析，新加入**相等子图**的边$$(x, y)$$，满足$$x \in X, y \in Y-T$$
并且有$$lx(x) + ly(y) = w(x, y)$$

另外还有，相等子图中，$$\text{slack}(y) = \min \\{lx(x) + ly(y) - w(x, y) \\}$$
每次迭代中，**新加入**的每个$$x \in S$$，都可能会对$$\text{slack}(y)$$有影响

![](/media/content_img/KM02.png)

> 用 bfs 来实现匈牙利算法

**基本算法框架**
1.迭代$$nx$$次，每次迭代都尝试找出**一条**增广路$$(ex, ey)$$，具体怎么找呢？

2.和朴素匈牙利算法框架一样，一开始时候`visx, visy, p, slack`数组清空
```bash
visx.assign(nx, 0), visy.assign(ny, 0)
slack.assign(ny, +infty)
p.assign(nx, -1)
```
先扩张$$S$$集，把未浸润的点，满足$$xy(x) = -1$$的$$x$$进队列（相当于`dfs(x)`）
然后进行`bfs`，每次取队头元素

3.注意到此时队列中的元素，都是满足$$xy(x) = -1$$的未匹配点，如果能够在**相等子图**中找到$$y \in Y$$
并且$$yx(y) = -1$$，那么$$(x, y)$$就是增广路，具体来说

考虑所有$$y \in Y-T$$（即`visy(y) = 0`）的点$$y$$，如果$$lx(x) + ly(y) = w(x, y)$$，那么$$(x, y)$$边属于相等子图

若$$y$$未浸润，$$yx(y) = -1$$，那么$$(ex, ey) = (x, y)$$，找到了增广路了，退出这一轮迭代
若$$y$$已经和$$yx(y)$$**匹配**，按朴素匈牙利做法，$$dfs(x) \to dfs(yx(y))$$（看看从`yx(y)`出发能不能找到`vis = 0`的邻居）
这里用`bfs`实现，则需要将`yx(y)`**进队列**，同时按照`dfs`的做法，要标记`visx(yx(y)) = visy(y) = 1`
另外新进入队列的`yx(y)`，要用它来更新`slack`数组

![](/media/content_img/KM03.png)

4.如果这样做，队列都清空了，遍历了一遍仍然找不到增广路怎么办？考虑**修改顶标**
修改顶标的方法如上面分析的那样，$$\delta = \min(\text{slack}(y), \quad y \in Y-T)$$
```bash
for y in Y, if visy[y] == 0:
	delta = min(delta, slack[y])
	
for x in X:
	if visx[x] == 1:		lx[x] -= delta
	
for y in Y:
	if visy[y] == 1:		ly[y] += delta
	else slack[y] -= delta
```
修改完顶标之后，$$y \in Y-T$$中，能进入相等子图的边，满足$$\text{slack}(y) = 0$$
并且$$(slackx(y), y)$$这个相等子图的边，可能是增广路径，具体是不是呢？和之前的做法一样

若$$y$$未浸润，即`yx[y] == -1`，那么$$(ex, ey) = (slackx(y), y)$$找到了增广路，退出迭代
若$$y$$已经和$$yx(y)$$匹配上了，同样需要`dfs(yx(y))`，看看有没有`vis = 0`的点，可以继续增广
用`bfs`来模拟，就是将`yx(y)`进队列，同时`p( yx(y) ) = slackx(y)`这是用来**回溯的**
依次更新`visx(yx(y)) = visy(y) = 1`，同时用`yx(y)`来更新`slack(y)`

> 接下来考虑如何统计最大权，即匹配边的权值和

![](/media/content_img/KM04-01.png)

接着考虑计算最大权
![](/media/content_img/KM04-02.png)

模拟`dfs`的回溯，$$x \to p(x)$$，$$y \to ty$$，依次把匹配边的权值加上
```bash
迭代，权值代价，从上一次迭代，转移过来
costs[ cur + 1 ] = costs[cur]

一开始的时候，令 (x, y) = (ex, ey)，并且端点处，新加入的边默认是匹配的
costs[cur + 1] += w(x, y)

如果发现 xy[x] != -1，那么需要交错路取反，之前的 (x, xy[x]) 要从匹配的，改成非匹配的
costs[cur + 1] -= w(x, xy[x])

然后令 ty = xy[x], xy[x] = y, yx[y] = x，更新当前的匹配边
继续回溯，x = p[x], y = ty
```

## 稳定匹配和求婚算法
定义，假设说需要$$n$$对稳定的婚姻，但是$$x, y$$分别匹配给其他人，却发现$$x$$喜欢$$y$$胜过当前的配偶
同时，$$y$$喜欢$$x$$也胜过当前的配偶，那么认为未匹配对$$(x, y)$$是一个**不稳定对**

如果一个完美匹配，没有不稳定的未匹配对，称为**稳定匹配**

### Gale-Shapley 求婚算法
给定男子和女子各自的偏好序列
**迭代求解**
1.每名男子向偏好序列最前面的，仍未拒绝过他的女子求婚
2.如果每位女子只收到一个人的求婚，那么算法结束，并且得到一个稳定匹配
3.否则的话，女子会收到多个求婚的男子，作为候选人序列来考虑，女子只对候选人序列中，偏好最靠前的人说**接受**

**定理** 求婚算法能够产生一个稳定匹配，迭代最多进行$$O(n^2)$$次

观察到一个关键的性质
每名男子的求婚序列，是**非严格单调减**的，而每个女子**说了接受**的候选人序列，是**非严格单调增的**
直观点说，男子一直尝试对心仪的女子表白，被拒绝了，就接着下一个
而每名女子，会向同一名求婚男子，说**接受**，直到下一个**更喜欢的**求婚者到来

这个可以用反证法来证明
假设说，存在不稳定匹配对$$(x, a)$$，意味着，实际上产生的匹配是$$(x, b), (y, a)$$，这意味着什么呢？
1.实际的结果，$$y \leftrightarrow a$$配对，说明$$x$$从来没有对$$a$$求过婚，否则$$a$$更喜欢$$x$$
应该尝试匹配$$x$$和$$a$$，而不是$$(y, a)$$

2.另一方面，$$x \leftrightarrow b$$配对，因为$$x$$更喜欢$$a$$，所以充要条件是$$x$$向$$a$$**求婚，却被拒绝**
根据之前的分析，$$x$$从未向$$a$$求过婚，矛盾了

## 快速二部匹配
### 基本结论
**结论1**，设$$M$$是一个大小为$$r$$的匹配，$$M^{\prime}$$是一个大小为$$s > r$$的匹配
则至少存在$$s-r$$条无公共顶点的增广路径，至少可以在$$M \Delta M^{\prime}$$中找到这些路径

这个结论挺好证明的，在大小为$$r$$的匹配中，每次可以从$$s-r$$中任选一条匹配边加入
因为是匹配，两条匹配边之间是没有公共顶点的，所以结论成立

**结论2**
如果$$P$$是一条最短的$$M-$$增广路径，$$P'$$是$$M \Delta P-$$增广路径，则$$|P'| \geqslant |P| + 2|P \cap P'|$$
（将$$P$$看成边的集合）

```math
\begin{cases}
M \to (P' = (M \Delta P)) \\
(M \Delta P) \to (N = (M \Delta P)\Delta P')
\end{cases}
```
增广 2 次，一次增广仅加入一个最小单位，所以$$|N| = |M| + 2$$
另外，根据结论 1，不难发现$$N$$是一个大小比$$M$$多$$2$$的匹配，也就是说
在$$M \Delta N$$中，至少存在$$2$$条没有公共顶点的增广路径$$P_1, P_2$$，每一条至少与$$P$$一样长
因为$$P$$是最短的增广路径单位

交错路在延展的时候，需要**交错路取反**操作，那么$$(M \leftrightarrow P', P' \leftrightarrow N)$$存在取反操作
一条边$$\in M$$，它需要取反$$P'$$的边得到
从而一条边仅$$\in M \text{ or } \in N$$，当且仅当它$$\in P \text{ or } \in P'$$，从而$$M \Delta N = P \Delta P'$$
这样，我们有$$|P \Delta P'| \geqslant |P_1| + |P_2| \geqslant 2|P|$$
从而$$2|P| \leqslant |P \Delta P'| = |P| + |P'| - 2|P \cap P'|$$，即$$|P'| \geqslant |P| + 2|P \cap P'|$$

上面的形式化证明比较抽象，可以看下面的图

**引理**，如果$$P_1, P_2, \cdots$$是由前后相继的最短增广路径构成的序列，则相同的增广路径没有公共顶点

和结论2的证明如下图
![](/media/content_img/KM05.png)

引理的说明如下
![](/media/content_img/KM06.png)

**Hopcroft-Karp时间复杂度**
在具有$$n$$个顶点，$$m$$条边的二分图中，使用 bfs 策略阶段化最大匹配算法，时间复杂度是$$O(m\sqrt{n})$$

1.对所有未浸润点，进行多路增广，得到的路径是没有公共顶点的（根据引理可得），每一次都可以得到更长的增广路径
可以在$$O(m)$$复杂度内，得到我们需要的，具有某种长度的增广路径

2.将增广路径的序列，按长度排成$$P_1, P_2, \cdots, P_s$$，首先，匹配的大小$$s = \alpha^{\prime}(G) \leqslant n / 2$$
只要证明，$$P_1, P_2, \cdots P_s$$是构造某个最大匹配所需要的，前后相继的最短增广路
并且这些路径的长度，有$$\leqslant 2\lfloor \sqrt{s}\rfloor + 2$$个不同的取值，即可完成证明

考虑到增广到某个阶段，得到一个匹配$$|M_r| = r$$，但没有达到最大匹配$$|M_s|$$，这个时候
我们有$$s-r$$条，没有公共顶点的$$M_r-$$增广路径（这些边可以任意选一条，加入匹配）

> 考虑这些增广路径中，最短的一条路径

可以看作有$$s-r$$个非浸润点，要想让增广路尽可能短，不妨看成$$s-r$$组，每一组配上一条**浸润边**
这样，最短的一组，有$$\lfloor \dfrac{r}{s-r} \rfloor$$条来自$$|M_r|$$的边

另一方面，`|边集| >= |点集|`，不妨令$$s - r = t$$，那么有$$\dfrac{s-t}{t} \geqslant t$$，从而$$t = O(\sqrt{s})$$
那么令$$r = \lfloor s-\sqrt{s} \rfloor$$
我们可以推出$$|P\_{r+1}| \leqslant 2 \lfloor r / (s-r) \rfloor + 1$$
又因为$$\lfloor r / (s-r) \rfloor = O(s / \lceil \sqrt{s} \rceil) = O(\lfloor \sqrt{s} \rfloor)$$

因为增广路径的长度是**奇数**，所以可以推出增广路径的长度是$$2\lfloor \sqrt{s} \rfloor + 1$$
最多有$$2\lfloor \sqrt{s} \rfloor + 2$$个不同的长度值

## 匈牙利算法的其他问题探讨
### 公交车驾驶员问题
有$$n$$名驾驶员，$$n$$条上午路线，行车时间是$$x_1, x_2, \cdots, x_n$$
同时有$$n$$条下午路线，行车时间是$$y_1, y_2, \cdots y_n$$，如果一名司机在上午路线和下午路线行车总时间超过$$t$$
那么有加班费，现在要求分配路线，使得总加班费最少
证明，对任意司机$$i$$，为其分配第$$i$$长的上午路线，和第$$i$$短的下午路线，产生最优解

**算法分析**
证明如下图
![](/media/content_img/KM07.png)

### 其他练习
**问题1**
令矩阵$$A$$中的元素满足$$w(i, j) = a_ib_j$$，其中$$a_1, a_2, \cdots, a_n$$是和行关联的数，$$b_1, b_2, \cdots, b_n$$是和列关联的数
确定$$A$$中截断的最大权值

> 可以根据**排序不等式**

不妨设$$a_1 \geqslant a_2, b_1 \geqslant b_2$$，那么$$a_1b_1 \geqslant a_2b_2$$
将$$a$$从大到小排序，$$b$$从大到小排序，那么$$A \to B$$集的截断，有最大权值

**问题2**
数学系为$$n$$名学生开设$$k$$个讨论班，各个讨论班有不同的主题。每一名学生参加一个讨论班
第$$i$$个讨论班可以容纳$$k_i$$名学生，并且$$\sum k_i = n$$
每名学生提交了一个表单，将$$k$$个讨论班按照其偏好程度排序，将学生分配到各个讨论班
如果不存在两个学生，使得交换他们的讨论班之后，两者都更满意，那么我们称这个讨论班分配方案是稳定的
给出求稳定匹配的算法

> 考虑拆点

将第$$i$$个讨论班拆成$$k_i$$个点，每个学生有一个偏好序列，对于第$$x$$个学生，假设它考虑第$$y$$个讨论班
那么第$$y$$个讨论班有$$k_y$$个点，$$(x, y(k_y))$$分别连边，权值是$$k - \text{rank}$$
即偏好序列越靠前的讨论班，权值越大

建好图之后，求最大权匹配

**问题3**
假设有$$n$$名男子和$$n$$名女子，每个人为其偏好序列中第$$i$$个人打分为$$n - i$$，各配偶对的分数
是二人各自在对方偏好序列中所获得的分数之和，构造一个例子，使得最大权匹配，不是稳定匹配
![](/media/content_img/KM08.png)

**问题4**
求婚算法中，如果男子$$x$$和女子$$a$$在某个稳定匹配中，配对了，那么在男子求婚的条件下
Gale-Shapley 求婚算法中，$$a$$不会拒绝$$x$$
由此得出结论，在所有稳定匹配中，任意男子对这一算法产生的匹配最满意

考虑到$$a$$拒绝$$x$$，说明$$a$$的优先级队列中，形如$$(y, x)$$，并且$$y$$向$$a$$求婚
而$$y$$向$$a$$求婚，却有稳定匹配$$(y, b)$$，说明$$b$$的优先级高于$$a$$

否则的话，$$y \leftrightarrow a$$，$$y$$有优先级$$(a, b)$$，同时$$a$$有优先级$$(y, x)$$
那么$$(y, a)$$才是稳定匹配，而不是$$(y, b)$$

### 稳定室友问题
**问题1**
共有$$2n$$个人，每个人均将其他$$2n-1$$个人，按其偏好排序，在一个完美匹配中，如果没有未匹配的两个人
使得他们对彼此的偏好程度，都高于当前的室友，则匹配是稳定的
证明，下面的偏好序列，不存在稳定匹配
```math
a: b > c > d \\
b: c > a > d \\
c: a > b > d \\
d: a > b > c
```

```bash
分类讨论
(a, b) and (c, d)
(a, c) and (b, d)
(a, d) and (c, b)
```

**问题2**
稳定室友问题中，每个人都把偏好序列前面部分的人，看作**可接受的**，定义一个可接受图
其顶点是所有的人，边是彼此将对方列为可接受的人员对
证明，可接受图为$$G$$的偏好序列集合，可以产生一个稳定匹配，当且仅当$$G$$是二分图

> 不是二分图，就有奇环，从这个角度来考虑

1.如果是二分图，那么**可接受的对**，可以划分成两个部集，考虑划分成集合$$X, Y$$
执行 Gale-Shapley 求婚算法，可以得到一个稳定匹配

2.否则的话，图中有**奇环**，奇环是没有办法划分成两个集合的，必须要**删除一条边**，假设删除的可接受边是$$(x_1, x_2)$$
那么最后匹配起来是$$(x_1 \neq x_2), (x_1, a), (x_2, b)$$，$$\neq$$表示$$(x_1, x_2)$$没有匹配在一起
很明显，此时$$(x_1: x_2 > a > \cdots), \quad (x_2: x_1 > b > \cdots)$$
不难发现，$$(x_1, x_2)$$虽然没有匹配在一起，但是他们的**吸引力**是最高的，这是不稳定匹配

其实，换句话说，把**吸引力最高**的**可接受边**，断开，会产生一个不稳定匹配

上一篇：支配集，支配集常见的结论下一篇：字符串算法（一）：Z 函数，kmp 算法

看完文章有啥想法