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

Question

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

但是，我无法为当前场景应用该算法(构建图表)。

事情是这样的:我有“n”个男孩和“m”个女孩。他们每个人都有一个“舞蹈技能”，一个男孩可以与另一个女孩配对，前提是他们中的任何一个的技能差异相差 1 分。即绝对值(男技能-女技能)<=1。我必须找到可以形成的最大对数。

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

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

有人能帮帮我吗？

这是我的代码。如前所述，匹配算法是正确的。需要注意的是我构建图表的“主要”功能:

#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。我的代码返回 4，这是错误的。

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

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

任何帮助将不胜感激

Answer 1

问题出在构建图形的第二行。 我们不能有相同的男孩和女孩配对指数。所以正确的格式是:

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

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