Bipartite Matching Kuhn Algorithm
The Kuhn Algorithm, also known as the Hungarian algorithm, is a widely-used technique for solving the maximum bipartite matching problem. This algorithm is based on augmenting paths and was first proposed by Harold Kuhn in 1955 as an efficient solution to the assignment problem. In bipartite graphs, a matching is a collection of non-overlapping edges, and the objective of the maximum bipartite matching problem is to find a matching with the maximum number of edges. The Kuhn Algorithm achieves this by iteratively searching for augmenting paths in the graph and updating the matching accordingly.
In the context of the Kuhn Algorithm, an augmenting path is a simple path that starts and ends with free vertices (vertices not included in the current matching) and alternates between unmatched and matched edges. The algorithm begins with an empty matching and then iteratively searches for augmenting paths using a depth-first search (DFS) approach. Once an augmenting path is found, the algorithm updates the matching by flipping the edges' status along the path, effectively increasing the size of the matching by one. This process is repeated until no more augmenting paths can be found, at which point the algorithm terminates and returns the maximum matching. The Kuhn Algorithm is notable for its simplicity and effectiveness, with a time complexity of O(n * m) for n vertices and m edges in the bipartite graph.
/**************************************************************************************
Kuhn algorithm for maximum matching in bipartite graph. Works in O(N * M)
More about it: http://e-maxx.ru/algo/kuhn_matching
Based on problem 1683 from informatics.mccme.ru:
http://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=1683
**************************************************************************************/
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
using namespace std;
const int MAXN = 105;
int n, m;
vector <int> g[MAXN];
bool used[MAXN];
int mt[MAXN];
int ans;
bool kuhn(int v) {
if (used[v])
return false;
used[v] = true;
for (int i = 0; i < (int) g[v].size(); i++) {
int to = g[v][i];
if (mt[to] == 0 || kuhn(mt[to])) {
mt[to] = v;
return true;
}
}
return false;
}
int main() {
//assert(freopen("input.txt","r",stdin));
//assert(freopen("output.txt","w",stdout));
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int can;
scanf("%d", &can);
if (can)
g[i].push_back(j);
}
}
for (int i = 1; i <= n; i++) {
memset(used, 0, sizeof(used));
if (kuhn(i))
ans++;
}
printf("%d\n", ans);
return 0;
}
