如何在给定的当前通用场景中正确构建 Hopcroft Karp 最大匹配算法的图形？

Question

我正在解决一个算法问题，这需要我学习最大匹配算法。花了一天时间从各种渠道学习和实现，我已经理解了算法。

但是，我无法为当前场景应用算法（构建图表）。

事情是这样的：我有 'n' 个男孩和 'm' 个女孩。他们每个人都有一个 'Dancing Skill' 并且一个男孩可以与另一个女孩配对，前提是他们中的任何一个的技能差异相差 1 点。即绝对值（男技能-女技能）<=1。 我要找出最多可以组成的对数

我很确定我对 Hopcroft Karp 最大匹配算法的实现是正确的。问题是图形的构建。我尝试以复杂度 O(n*m) 的以下方式构建图表：

对于索引为1到n的每个男孩，搜索技能差异相差1分的女孩的索引。如果找到，请向图中添加一条无向边。 这对我来说似乎完全正确。

有人可以帮我吗？

这是我的代码。如前所述，匹配算法是正确的。需要注意的是我构建图表的 'main' 函数：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
#define pb push_back
#define sz 100001

int boysSkillz[sz], girlsSkillz[sz];

//Maximal Matching begins
vector<int> adj[sz];
int pairU [sz], pairV[sz], dist[sz];

bool HK_Bfs(int m)
{
    queue<int> Q;
    for (int u=1; u<=m; u++)
    {
        if (pairU[u]==0)
        {
            dist[u] = 0;
            Q.push(u);
        }
        else
            dist[u] = INT_MAX;
    }
    dist[0] = INT_MAX;
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        if (dist[u] < dist[0])
            for (int v:adj[u])
                if (dist[pairV[v]] == INT_MAX)
                {
                    dist[pairV[v]] = dist[u]+1;
                    Q.push(pairV[v]);
                }
    }
    return (dist[0] != INT_MAX);
}

bool HK_Dfs(int u)
{
    if (u != 0)
    {
        for (int v: adj[u])
            if (dist[pairV[v]] == dist[u]+1 && HK_Dfs(pairV[v]))
            {
                pairV[v] = u;
                pairU[u] = v;
                return true;
            }
        dist[u] = INT_MAX;
        return false;
    }
    return true;
}

int HopcroftKarp(int m, int n)
{
    for (int u=0; u<m; u++)
        pairU[u] = 0;
    for (int v=0; v<n; v++)
        pairV[v] = 0;
    int maxMatching = 0;

    while (HK_Bfs(m))
        for (int u=1; u<=m; u++)
            if (pairU[u]==0 && HK_Dfs(u))
                maxMatching++;
    return maxMatching;
}
//Maximal Matching ends

int main()
{
    int n, m;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>boysSkillz[i];
    cin>>m;
    for(int i=1;i<=m;i++)
        cin>>girlsSkillz[i];
    for(int i=1;i<=n;i++) //Building graph according to logic mentioned
        for(int j=1;j<=m;j++)
            if(abs(boysSkillz[i]-girlsSkillz[j])<=1)
            {
                adj[i].pb(j);
                adj[j].pb(i);
            }
    cout<<HopcroftKarp(n,m);
    return 0;
}

输入如下。 'n'是男生的个数。然后 'n' 整数表示他们的技能。 'm'是女生的数量。然后 'm' 整数表示他们的技能。

例如：

4
1 4 6 2
5
5 1 5 7 9

上述输入的正确输出是 3。我的代码 returns 4 是错误的。

一切都在行动：http://ideone.com/WOcE8I

这是实际问题的 link：http://codeforces.com/problemset/problem/489/B

任何帮助将不胜感激

Answer 1

问题出在构建图表的第二行。 我们不能让男孩和女孩的指数相同。所以正确的格式是：

adj[i].pb(j);
adj[j+n].pb(i); //This ensures indices assigned are distinct

这解决了问题，在为最大匹配构建二分图时应始终记住这一点

如何在给定的当前通用场景中正确构建 Hopcroft Karp 最大匹配算法的图形？

How do I correctly build my graph for the Hopcroft Karp Maximal Matching Algorithm in the current generic scenario given?

c++

algorithm

graph

matching