Bipartite Matching - Max Flow Algorithm

Converting Bipartite Matching to Max Flow Algorithm

//This is conversion from Bipartite matching to Max-FLow algorithm.
//Nice way to convert.
//I have used EdmondsKarp algorithm for the conversion.
class PointyWizardHats {
 public:
 int graph[205][205],lnode,rnode,parent[205],visited[200],city;
 bool bfs(int s,int t) 
{
  parent[s]=-1;
  visited[s]=true;
  queue<int> Q;
  Q.push(s);
  while(!Q.empty())
  {
    int u=Q.front();
    Q.pop();
    if(u==t)
      return true;
    for(int v=0;v<city;v++)
    {
      
      if(!visited[v] and graph[u][v]>0)
      {
        Q.push(v);
        visited[v]=true;
        parent[v]=u;
      }
    }
  }
  return false; 
}
int maxflow(int s,int t)
{
   int mflow=0;
   CLR(visited);
   CLR(parent);
   while(bfs(s,t))
   {
    
    CLR(visited);
    int v,u;
    int mi=10000000;
    for(v=t;v!=s;v=parent[v]){u=parent[v];
      mi=min(mi,graph[u][v]);}
    for(v=t;v!=s;v=parent[v])
    {
     u=parent[v];graph[u][v]-=mi;graph[v][u]+=mi;
    }     
    mflow+=mi;
   }
   return mflow; 
}
 
 bool can_be_kept(int bh,int br,int th,int tr) // General Constraint for the problem
 {
  if(br>tr and (th*br>bh*tr))
    return true;
  return false; 
 }
 
 int getNumHats(vector <int> topHeight, vector <int> topRadius, vector <int> bottomHeight, vector <int> bottomRadius) 
 {
  CLR(graph);
  lnode=bottomHeight.size();
  rnode=topHeight.size();
  for(int i=0;i<lnode;i++) 
    graph[0][i+1]=1; //Where 0 is the source it connects to all the u nodes .
  for(int i=0;i<lnode;i++) //Now take all the u nodes starting from 1 to lnode-
    for(int j=0;j<rnode;j++)
      if(can_be_kept(bottomHeight[i],bottomRadius[i],topHeight[j],topRadius[j]))
         graph[i+1][lnode+j+1]=1;
  
  for(int i=0;i<rnode;i++)
    graph[lnode+i+1][rnode+1+lnode]=1;
  city=rnode+lnode+2;
  return maxflow(0,rnode+1+lnode); 
 }
};

Bipartite-Matching

/*First METHOD 
Solved Using kuhn's Algorithm 
Kho-Kho algorithm ~ Take a free vertex and find a augmentation which increase the match atleast by one.
Berge's Theorem ~ A matching M in a Bipartite graph is maximum if and only if there doesn exist any augmenting path.
Run in O(N*M+N*N) */ 
class PointyWizardHats {
 public:
 int parent[55],visited[55],rnode,lnode;
 vector<int> graph[55];
 bool can_be_kept(int bh,int br,int th,int tr) // General Constraint for the problem
 {
  if(br>tr and (th*br>bh*tr))
    return true;
  return false; 
 }
 bool dfs(int u)
 {
   if(visited[u])
      return false;
   visited[u]=true;
   for(int i=0;i<(int)graph[u].size();i++)
   {
     int v=graph[u][i];
     if(parent[v]==-1 or dfs(parent[v]))
     {
       parent[v]=u;
       return true;
     }
   }
   return false;
 }
 int kuhn_salgo()
 {
   SET(parent);  
   for(int i=0;i<lnode;i++)  
   { 
    CLR(visited);  
    dfs(i);
   }
   return rnode-count(parent,parent+rnode,-1);   
 }
 int getNumHats(vector <int> topHeight, vector <int> topRadius, vector <int> bottomHeight, vector <int> bottomRadius) 
 {
  lnode=bottomHeight.size();rnode=topHeight.size();
  LOOP(j,rnode)
   LOOP(i,lnode)
     if(can_be_kept(bottomHeight[i],bottomRadius[i],topHeight[j],topRadius[j]))
        graph[i].push_back(j);
  
  return kuhn_salgo(); 
 }
};