Hungarian Matching Algorithm
The Hungarian Matching Algorithm, also known as the Kuhn-Munkres algorithm or Munkres assignment algorithm, is a combinatorial optimization technique that solves the assignment problem in polynomial time. The assignment problem is a classic optimization problem in which a set of tasks needs to be assigned to a group of agents in such a way that the total cost of performing the tasks is minimized. The algorithm was developed by Harold Kuhn in 1955, inspired by the earlier works of two Hungarian mathematicians, Dénes Kőnig and Jenő Egerváry, and later refined by James Munkres.
The Hungarian Matching Algorithm works on a bipartite graph, where nodes are divided into two disjoint sets such that all edges connect nodes from one set to the other. The algorithm begins by creating a cost matrix, representing the weight or cost associated with assigning each task to each agent. It then manipulates the cost matrix by subtracting the smallest value in each row and column, effectively normalizing the matrix. The algorithm then constructs a new bipartite graph based on the modified cost matrix, looking for perfect matchings (i.e., each task is assigned to exactly one agent) with zero cost. If such a perfect matching is found, the algorithm terminates, and the optimal assignment is returned. If not, the algorithm iteratively updates the cost matrix and searches for a perfect matching until the optimal assignment is found.
/***************************************************************************************************
Hungarian matching algorithm - O(N ^ 3)
Based on problem http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=394#1
Algorithm realization based on http://e-maxx.ru/algo/assignment_hungary
***************************************************************************************************/
#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;
const int INF = 1000 * 1000 * 1000;
int n;
int a[MAXN][MAXN];
int u[MAXN], v[MAXN], link[MAXN], par[MAXN], used[MAXN], minval[MAXN];
int main() {
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%d", &a[i][j]);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < MAXN; j++) {
used[j] = false;
minval[j] = INF;
}
int j_cur = 0;
par[j_cur] = i;
do {
used[j_cur] = true;
int j_next, delta = INF, i_cur = par[j_cur];
for (int j = 0; j <= n; j++)
if (!used[j]) {
int cur = a[i_cur][j] - u[i_cur] - v[j];
if (cur < minval[j]) {
minval[j] = cur; link[j] = j_cur;
}
if (minval[j] < delta) {
delta = minval[j]; j_next = j;
}
}
for (int j = 0; j <= n; j++)
if (used[j]) {
u[par[j]] += delta; v[j] -= delta;
}
else {
minval[j] -= delta;
}
j_cur = j_next;
} while (par[j_cur]);
do {
int j_prev = link[j_cur];
par[j_cur] = par[j_prev];
j_cur = j_prev;
} while (j_cur > 0);
}
printf("%d", -v[0]);
return 0;
}
