[UVa Live] 6811 - Irrigation Lines

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 6811 - Irrigation Lines
Source            : UVa Live Archive
Category          : Graph Theory
Algorithm         : Maximum Bipartite Matching 2D, Kuhns Algorithm
Verdict           : Accepted

#include "bits/stdc++.h"  
   
using namespace std;  
   
static const int maxn = 500 + 5;  
   
vector <int> bipertite_graph[maxn];  
int row, column;  
   
inline void addEdge(int u, int v)  
{  
      bipertite_graph[u].push_back(v);  
      bipertite_graph[v].push_back(u);  
}  
   
inline void clean()  
{  
      for (int i = 0; i < maxn; i++) bipertite_graph[i].clear();  
}  
   
int Left[maxn], Right[maxn], seen[maxn];  
   
inline bool kuhn(int u)  
{  
      for (int v : bipertite_graph[u])  
      {  
            if (seen[v]) continue;  
            seen[v] = 1;  
            if (Right[v] == -1 || kuhn(Right[v]))  
            {  
                  Right[v] = u;  
                  Left[u] = v;  
                  return 1;  
            }  
      }  
      return 0;  
}  
   
inline int bpm()  
{  
      for (int i = 0; i < maxn; i++) Left[i] = Right[i] = -1;  
      int match = 0;  
      for (int i = 1; i <= row; i++)  
      {  
            for (int j = 0; j < maxn; j++) seen[j] = 0;  
            if (kuhn(i)) match++;  
      }  
      return match;  
}  
   
int main()  
{  
      //freopen("in.txt", "r", stdin);  
   
      int tc;  
      cin >> tc;  
      for (int tcase = 1; tcase <= tc; tcase++)  
      {  
            cin >> row >> column;  
            string s;  
            for (int i = 1; i <= row; i++)  
            {  
                  cin >> s;  
                  for (int j = 1; j <= column; j++)  
                  {  
                        if (s[j-1] == '1') addEdge(i, j + row);  
                  }  
            }  
            int maximum_bipertite_matching = bpm();  
            cout << "Case #" << tcase << ": " << maximum_bipertite_matching << endl;  
            clean();  
      }  
}