一类匹配问题的求解及应用
本文地址：blog.lucien.ink/archives/506
本篇以应用为主，不涉及算法细节
0. 前言
在生活当中有很多场景都可以抽象为多对多匹配问题，比如网约车和外卖派单、会员偏好分配、相亲问题等，可以观察出来，这些问题其实都可以抽象为 $N$ 个物品分配给 $M$ 个人，也就是本文所说的“一类匹配问题”。
大部分时间可以用二分图或者是网络流来解这类问题，小部分时候图论无法满足业务上的强约束，便只能考虑其它算法了。
一般来说，二分图能解决的问题网络流都可以解决，反之不行。
1. 相亲问题
假设有 $N$ 个男生和 $M$ 个女生，如果第 $i$ 个男生可以和第 $j$ 个女生配对，那么在下图中他们俩就会被一条边相连。
算法目标为让配对数量最多。
可以看出，$男_1$ 和 $女_2$、$男_2$ 和 $女_1$ 相匹配是最优的。
对应的解法为二分图，或者是最大流。
1.1 相亲问题 Plus
假设每对男生女生之间有一个契合度，求怎样配对可以在配对数量最多的前提下契合度总和最高。
$男_1$ 虽然和 $女_2$ 的契合度很高，但是为了满足配对数量最多，他们俩不能配对，所以最优的结果是 $男_1$ 和 $女_1$、$男_2$ 和 $女_2$，契合度的总和为 $140$。
对应的解法为带权二分图，或者是费用流。
2. 网约车派单
假设有 $N$ 个乘客，$M$ 辆车，每辆车最多可以载 $4$ 名乘客，如果第 $i$ 名乘客能被第 $j$ 辆车接到，那么在下图中他们就会被一条边相连。
可以看到，$车_2$ 可以接这 $5$ 名乘客中的任何一名，但是 $车_1$ 却只能接 $人_1$ 和 $人_2$，所以可行的分配方案之一就是 $车_1$ 去接 $人_1$，$车_2$ 去接剩下的所有人。
二分图虽然能够通过拆点来解决这个问题，但比较合适的解法是最大流。
2.1 网约车派单 S
每辆车去接每个乘客是需要一定路途时间的（单位：分钟），求怎样派单能够在接最多乘客的情况下，让路途时间总和最短。
可以发现，第 $2$ 节中提到让 $车_2$ 接 $4$ 个人的方案是不够优秀的，总共需要 60 分钟。
最优的派单方案是让 $车_1$ 去接 $人_1$ 和 $人_2$，$车_2$ 去接剩下的所有人，总共需要 35 分钟。
带权二分图虽然也能通过拆点来解决这个问题，但比较合适的解法是费用流。
2.2 网约车派单 S Plus
因为有的司机的车比较好，有的司机的车比较差，为了提高乘客的乘车体验，公司要求开好车的司机承接 $70\%$ 的客流量，开坏车的司机承接 $30 \%$ 的客流量。
问最多能载多少客。
这个问题就只能用最大流来求解了，解法是新建两个虚拟汇点，一个汇点只属于好车，另一个汇点只属于坏车，然后再流向真正的汇点，流量分别为 $70 \%$ 和 $30 \%$ 即可。
求解出来的最大流就是满足群体限流条件下的最大载客数量。
假设 $车_1$ 为好车，$车_2$ 为坏车，建图如下。
其中 $边集_1$ 和 $边集_2$ 的流量都为 $1$，$边集_3$ 的流量为每辆车的最大载客量，在这里统一为 $4$。
2.3 网约车派单 Pro
在 $2.2$ 节的基础之上，我们引入路途时间的概念，目标和 $2.1$ 节一样，求怎样派单能够在接最多乘客的情况下，让路途时间总和最短。
这个问题也只能用费用流来求解，图的结构和 $2.2$ 节一样，不同的是每条边会多一个权重。
$边集_2$ 的权重为路途时间，剩下所有边的权重为 $0$ 即可。
求出的最大流和 $2.2$ 一致，但是派单方案可能不一致。
2.4 网约车派单 Pro Max
假设出了新规定，每次载客的时候，最多载两个男生和两个女生，在满足这个要求和上述所有要求的前提下，求怎样分配能够让路途时间总和最小。
其中：
- $边集_1$ 的流量为 $1$，费用为 $0$
- $边集_2$ 的流量为 $1$，费用为路途时间
- $边集_3$ 的流量为 $2$，费用为 $0$
- $边集_4$ 的流量为每辆车的最大载客量，此处为 $4$，费用为 $0$
3. 小结
至此，我们借助网络流实现了在满足个体接单种类上限、个体流量控制、群里流量控制的前提下，求解最优匹配的功能。
虽然网络流是一个较为简单的算法，但网络流能实现的功能远不限于此。私以为，图论的精髓在于问题抽象与建图，而不是算法本身。本文只是列举了一类非常简单的例子，希望能对读者有一定的帮助。
4. 附录
4.1 最大流样例代码
Dinic，复杂度 $O(V^2E)$
4.2 最小费用最大流样例代码
简称费用流
最小费用最大流，复杂度 $O(最大流 \times O(SPFA))$
