﻿ Tips And Tutorial - Presented by Oneous!

Maximum Bipartite Matching
Last Update: 25 August, 2009

Problem: Suppose that in a group of n single women and n single men who desire to get married, each participant indicates who among the opposite sex would be acceptable as a potential spouse. This situation could be represented by a bipartite graph in which the vertex classes are the set of n women and the set of n men, and a woman x is joined by an edge to a man y if they like each other. For example we could have the women Ann, Beth, Christina, Dorothy Evelyn, and Fiona, and the men Adam, Bob, Carl, Dan, Erik, and Frank. If Ann liked Adam and Bob, (and vice-versa), Beth liked Adam and Carl, Christina liked Dan, Erik and Frank, Dorothy liked Bob, Evelyn liked Adam and Dan, and Fiona liked Frank, we would have the following bipartite graph. In this situation could we marry everybody to someone they liked? This is one version of the Marriage Problem.

My Code:

``````//Type: C++ Code for Bipartite Matching
//ACM Problem no: 10080 (Gopher II

#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cctype>
#include<iostream>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
#define INF  2147483647
#define EPS  0.000000001
#define MAX(a,b)  ((a>b)?a:b)
#define MIN(a,b)  ((a<b)?a:b)
#define SET(NAME,FROM,TO,BY)   {for(int _i=FROM;_i<=TO;_i++) NAME[_i]=BY;}
#define CLEAR(A,N)  (memset(A,0,(N)*sizeof(A[0])))
#define VI vector<int>
#define VIT vector<int>::iterator
#define MAPS map<string,int>
#define MAPSIT map<string,int>::iterator

typedef long double LD;
const int limit=110;
typedef struct
{
double x,y;
}inputType;
inputType gopher[limit],hole[limit];

/**************************************************************************/
/********************  Bipartite Matching  ********************************/
VI vA[limit],vB[limit];
int matA[limit],matB[limit],visited[limit];
int matchFound;

void findMatch(int s, int op)
{
int i,t;
if(matchFound)
return;

if(op%2==0)
{
if(visited[s])
return;
visited[s]=1;
for(i=0;i<vA[s].size() && matchFound==0;i++)
{
t=vA[s][i];
if(matB[t]==-1)
{
matchFound=1;
matB[t]=s;
matA[s]=t;
return;
}
else if(matB[t]!=s)
{
findMatch(t,op+1);
if(matchFound)
{
matA[s]=t;
matB[t]=s;
return;
}
}
}
}
else
{
findMatch(matB[s],op+1);
}
}

int BipartiteMatch(int n, int m) // n = matA's size ; m= matB's siz
{
int i,j,t,total;

for(i=0;i<n;i++) matA[i]=-1;
for(i=0;i<m;i++) matB[i]=-1;
total=0;

// initialize each connection with one another if possibl
for(i=0;i<n;i++)
{
for(j=0;j<vA[i].size();j++)
{
t=vA[i][j];
if(matB[t]==-1)
{
matB[t]=i;
matA[i]=t;
total++;
break;
}
}
}

//find a unmatched node of A and match it if possibl
for(i=0;i<n;i++)
{
if(matA[i]==-1)
{
CLEAR(visited,n+1);
matchFound=0;
findMatch(i,0);
if(matchFound)
total++;
}
}

}

/*************** END of B-match *************************
**********************************************************/

void reset(int n, int m)
{
int i;
for(i=0;i<n;i++)
vA[i].clear();
for(i=0;i<m;i++)
vB[i].clear();
}

int main()
{
//freopen("in.txt","rt",stdin)
//freopen("out.txt","wt",stdout)
int i,j,n,m;
double d,s,v,speed;

while(scanf("%d %d %lf %lf",&n,&m,&s,&v)==4)
{
for(i=0;i<n;i++)
scanf("%lf %lf",&gopher[i].x,&gopher[i].y);
for(i=0;i<m;i++)
scanf("%lf %lf",&hole[i].x,&hole[i].y);
speed=s*v;
for(i=0;i<n;i++)
{
for(j=0;j<m;j++)
{
d=sqrt( (gopher[i].x-hole[j].x)*(gopher[i].x-hole[j].x) + (gopher[i].y-hole[j].y)*(gopher[i].y-hole[j].y) );
if(d<=speed)
{
vA[i].push_back(j);
vB[j].push_back(i);
}
}
}

printf("%d\n",n-BipartiteMatch(n,m));
reset(n,m);
}

// End of main function.......
return 0;
}

/***  Programmed by:
###########################
##   ~  ORONNO  ~		 ##