Как правильно построить мой график для алгоритма максимального соответствия Хопкрофта Карпа в данном заданном обобщенном сценарии?

Question

Я решаю алгоритмическую задачу, которая потребовала от меня изучения алгоритма максимального соответствия. Потратив день на изучение и реализацию этого из различных источников, я понял алгоритм.

Однако я не могу применить алгоритм (построить график) для текущего сценария.

Вот и все: у меня есть "n" мальчиков и "m" девочек. У каждого из них есть "Танцевальный навык", и мальчик может быть в паре с другой девушкой, если разница в их навыке отличается на 1 очко. То есть абсолютное значение (навык мальчик-девушка навык)<=1. Я должен найти максимальное количество пар, которые могут быть сформированы.

Я уверен, что моя реализация алгоритма максимального соответствия Хопкрофта Карпа верна. Проблема в построении графа. Я попытался построить график следующим образом в сложности 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 целых чисел за их навык.

Например:

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

Это решает проблему и всегда следует помнить при построении двудольного графа для максимального соответствия