c++ - 最大二分匹配 C++

Question

我正在解决一个类的两个 vector 的匹配问题

class matching
{
public:
    int n;
    char match;
};

这是我正在尝试实现的算法:

int augment(vector<matching> &left, vector<matching> &right)
{
   while(there's no augmenting path)
     if(condition for matching)
        <augment>
  return "number of matching";
}

对于粗略匹配，如果left[i]与right[j]匹配，则left[i].n = j 、 left[i].match ='M' 、right[j].n = i 和 right[j].match = 'M' code> 和不匹配的成员有成员 n = -1 和 match = 'U'

在查找增广路径时，如果一条路径存在于另一条路径 (i, j)，则我们将不匹配路径的成员 match 从 'M' 更改为当我们更改时，'U' 及其 n = -1 以及与增广路径匹配的两个成员 match 更改为 'A'根据其索引，其成员n。

我不知道这是否是解决这个问题的正确方法，这是我第一次尝试最大匹配，我已经阅读了很多文章并在线观看了教程，但我无法获取我的“代码”正常运行。

我不需要代码，我可以编写我的代码。我只是想一步一步地理解这个算法。如果有人能给我一种像我上面尝试的算法那样的算法，我将不胜感激。另外，如果我从那时起就走错了方向，请纠正我。

Answer 1

我不确定您是否正确找到了增广路径。我建议采用以下方法。

1. 以贪心的方式寻找初始匹配。为了获得这一点，我们遍历左侧的每个顶点，并贪婪地尝试将其与右侧的一些空闲(不匹配)顶点进行匹配。

2. 尝试在图中找到一条增广路径 P。为此，我们需要从左侧的所有自由顶点开始进行广度优先搜索，并在搜索中交替搜索匹配和不匹配的边。 (即第二层包含与第一层相邻的所有右侧顶点 顶点，第三层包含所有左侧顶点 匹配2级顶点，第四级包含所有右侧 与 3 级顶点相邻的顶点等)。当我们停止搜索时 访问任何 future 级别的自由顶点并计算增广路径 P 使用目前计算出的广度优先搜索树。

3. 如果上一步能找到增广路径P:将P中匹配边和不匹配边分别改为不匹配边和匹配边，然后转到步骤2。

4. 否则:得到的结果匹配最大。

该算法需要对每个增强进行广度优先搜索，因此最坏情况的复杂度为O(nm)。虽然Hopcroft-Karp algorithm可以为每个广度优先搜索执行多次增强，并且具有更好的最坏情况复杂度，它 似乎(来自维基百科文章)实践中它并没有更快。