I'm solving an algorithmic problem which required me to learn a Maximal Matching algorithm. After spending a day learning and implementing it from various sources, I have understood the algorithm.
However, I'm unable to apply the algorithm (build the graph) for the current scenario.
Here it goes: I have 'n' boys and 'm' girls. Each of them has a 'Dancing Skill' and a boy can be paired with another girl iff either of their skill difference differs by 1 point. That is, absolute value (boy skill-girl skill)<=1. I have to find the maximum number of pairs that can be formed.
I'm pretty sure my implementation of the Hopcroft Karp maximal matching algorithm is correct. The problem is the building of the graph. I have tried to build the graph in the following way in complexity O(n*m):
For each boy indexed 1 to n, Search for the indices of the girls whose skill difference differs by 1 point. If found, add an undirected edge to the graph. This seems entirely correct to me.
Could someone help me out?
Here is my code. As mentioned, the matching algorithm is right. The attention required is in the 'main' function where I build the graph:
#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;
}
The input is as follows. 'n' is the number of boys. Then 'n' integers for their skills. 'm' is the number of girls. Then 'm' integers for their skill.
Eg:
4
1 4 6 2
5
5 1 5 7 9
The correct output for the input mentioned is 3. My code returns 4 which is wrong.
Everything in action: http://ideone.com/WOcE8I
Here's the link to the actual problem: http://codeforces.com/problemset/problem/489/B
Any help will be much appreciated
The problem is in the second line of building the graph. We cannot have same indices of boys and girls being paired with each other. So the correct format would be:
adj[i].pb(j);
adj[j+n].pb(i); //This ensures indices assigned are distinct
This resolves the problem and should always be remembered while building a bipartite graph for max-matching
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments