知识卡片
二部匹配归约为单位容量流
把二部图左右两侧分别接到源点和汇点;源到左点、可行配对边、右点到汇的容量均为1。整数最大流中的单位流配对边组成匹配,源汇边容量保证每个顶点至多参与一次。
反向残量边允许重新安排已有配对;最大匹配的数量最优,但可能存在多个不同匹配。
234的左右集合应是不相交集合,并非没有跨集合连接;可行配对正是跨两侧的边。输出匹配大小最大,不保证唯一。
235的03388例子通过反向残量重新配对;03389–03390仅从pairs创建顶点映射,若集合有孤立元素,map.get可能为空;左右集合对象相等或编号与汇点构造不一致也需处理。实现应校验两侧成员、唯一标识和配对合法性。
236以n、m、k表示两侧大小和配对边数,构图 O(n+m+k),扫描配对边输出结果 O(k);最大流计算本身的成本不能省略。
243把任务分配建模为每一侧单位容量;若要求所有任务完成,须同时指定总匹配量或满足每个需求,而不能只最小化非负费用。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 二部匹配归约为单位容量流
- · 输入/输出
- · 解决方案
- · 分析
- · 任务分配问题
原书出处 · 5 处
- · 查看原书依据
二部图匹配 匹配问题有多种形式。我们考虑如下这种情况,五个求职者会面试五个职位。每个求职者都已经列出了满足能力要求的职位。现在的任务就是将尽可能多地分配工作给求职者,但是每份工作只能提供给一位求职者。我们会非常惊讶地发现可以使用Ford-Fulkerson算法来解二部图匹配问题。在计算机科学中,这种
- · 查看原书依据
配对集合中得到的一个配对集合(si,tj),P。这个集合的规模是最大能够匹配上的配对数目。算法保证不存在更多的匹配数(虽然会有其他的匹配方式能够得到同样多的匹配个数)。
- · 查看原书依据
流为1的边(si,tj),输出选中了匹配(si,tj)∈P。为了简化表述,例8-5的代码中删除了错误检测[1]。 例8-5:使用Ford-Fulkerson的二部图匹配 [1]要了解更多的细节,请参见代码库中的algs.model.network.matching.Bipartite-Matchin
- · 查看原书依据
O(k)的时间来将解映射成二部图问题的解。
- · 查看原书依据
任务分配问题 任务分配问题是转运问题的一个变种,有着更多的限制条件:每个供应节点只能供应一个单位,需求节点也只需要一个单位。