[UVa] 11419 - SAM I AM

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 11419 - SAM I AM
Source            : UVa Online Judge
Category          : Graph Theory
Algorithm         : Maximum Bipartite Matching 2D, Kuhns Algorithm
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
static const int maxn = 5e3 + 5;
 
vector <int> bipertite_graph[maxn];  // row -> column
int row, column, k;
 
int visrow[maxn], viscolumn[maxn];
int Left[maxn], Right[maxn], seen[maxn];
 
inline bool kuhn(int r)
{
      visrow[r] = 1;
      for (int c : bipertite_graph[r])
      {
            if (viscolumn[c] == 0)
            {
                  viscolumn[c] = 1;
                  if (Right[c] == -1 || kuhn(Right[c]))
                  {
                        Right[c] = r;
                        Left[r] = c;
                        return 1;
                  }
            }
      }
      return false;
}
 
inline int bpm()
{
      for (int i = 0; i < maxn; i++)
      {
            Left[i] = Right[i] = -1;
            visrow[i] = viscolumn[i] = 0;
      }
      int match = 0;
      for (int i = 1; i <= row; i++)
      {
            for (int j = 0; j < maxn; j++) viscolumn[j] = 0;
            if (kuhn(i)) match++;
      }
      return match;
}
 
int main()
{
      //freopen("in.txt", "r", stdin);
 
      while (cin >> row >> column >> k)
      {
            if (row == 0 && column == 0 && k == 0) break;
            for (int i = 0; i < k; i++)
            {
                  int x, y;
                  cin >> x >> y;
                  y += row;
                  bipertite_graph[x].push_back(y);
            }
            int maximum_bipertite_matching = bpm();
            printf("%d", maximum_bipertite_matching);
 
            for (int i = 0; i < maxn; i++) visrow[i] = viscolumn[i] = 0;
            for (int i = 1; i <= row; i++) if (Left[i] == -1) kuhn(i);
 
            for (int i = 1; i <= row; i++)
            {
                  if (!visrow[i]) printf(" r%d", i);
            }
            for (int i = row+1; i <= row+column; i++)
            {
                  if (viscolumn[i]) printf(" c%d", i - row);
            }
            puts("");
 
            for (int i = 0; i < maxn; i++) bipertite_graph[i].clear();
      }
}

[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();  
      }  
}