二部图的双匹配

Question

我在学习算法测试时遇到了以下问题，但没有给出答案：

1. 最大双匹配问题--给定一个二分图G=(V=(LUR)，E)，描述了一种算法，该算法对v中的每个顶点v返回一组边M.
2. 定义：“强双匹配”是V中每个顶点v的双匹配s.t，M中至少有一条边，其中包含v.给定二部图G=(V=(LUR)，E)和强双匹配M，描述了返回最大大小的强双匹配M‘的算法.证明你的答案。

所以我已经解决了

1)对最大流进行约简:将顶点的s、t和边从s增加到L，边从R增加到t，每个边的容量为2，并用无限容量定义L与R之间各边的容量。利用Dinic算法求出最大流，并返回L与R之间正流的所有边。

( 2)我考虑过以某种方式操纵网络，使每个顶点都有正流，然后用算法从某种程度上构造一个最大解。有什么想法吗？运行时限制为O(V^2E) (Dinics运行时)

Answer 1

下面是使用最小成本流的O(n^3)中的一个解决方案。

回想一下我们如何为标准的二部匹配建立一个网络。

1. 对于来自L的每个顶点u，添加一个从S到u的单位容量边；
2. 对于每个边u- v，其中u来自L，v来自R，则添加u到v的边，注意它的容量不重要，只要它至少是1；
3. 对于R中的每个顶点v，添加一个U到R的单位容量边。

现在，我们保持中心部分不变，左、右部分略有改变。

1. 对于L的每个顶点u，从S到u添加两个单元-容量边，其中一个具有成本-1，另一个具有成本0；

边v->S.

不考虑成本，这就是你自己建立的网络。这里的最大流对应于最大的双匹配。

现在，让我们找出尺寸k的最小成本流。它对应于一些双匹配，其中对应的匹配涉及最大可能的顶点数，因为接触一个顶点(即，至少推动单位流通过它)降低了1的成本。此外，第二次接触顶点并不会降低成本，因为第二边的成本是0。

我们是如何得到解的:对于每一个k= 1，.，2n迭代地找到最小成本流，并取对应于最小成本的值。

使用约翰逊算法 (也称为Dijkstra的带势)给出O(n^2)每次迭代，即O(n^3)的整体。

P.S.单位图上Dinic算法的运行时间较好，在二分图上达到O(E sqrt(V))。