Hungarian Algorithm
O(n²m)Minimum-cost assignment of n rows to m columns (n ≤ m) with the potentials method. Faster and simpler to use than min-cost flow for pure assignment problems. Everything is 1-indexed; row 0 and column 0 are sentinels. For maximization, negate the costs.
// use it on
UVa 10746: Crime Wave - The Sequel ↗
Assign police cars to banks at minimum total distance, a direct assignment-problem instance.
// the code
// a = cost matrix, 1-indexed: a[1..n][1..m], n <= m
// returns {min cost, assignment} with assignment[i] = column of row i
pair<long long, vector<int>> hungarian(vector<vector<long long>>& a) {
int n = a.size() - 1, m = a[0].size() - 1;
const long long INF = LLONG_MAX / 4;
vector<long long> u(n + 1), v(m + 1), minv(m + 1);
vector<int> p(m + 1), way(m + 1);
vector<bool> used(m + 1);
for (int i = 1; i <= n; i++) {
p[0] = i;
int j0 = 0;
fill(minv.begin(), minv.end(), INF);
fill(used.begin(), used.end(), false);
do {
used[j0] = true;
int i0 = p[j0], j1 = 0;
long long delta = INF;
for (int j = 1; j <= m; j++)
if (!used[j]) {
long long cur = a[i0][j] - u[i0] - v[j];
if (cur < minv[j]) minv[j] = cur, way[j] = j0;
if (minv[j] < delta) delta = minv[j], j1 = j;
}
for (int j = 0; j <= m; j++)
if (used[j]) u[p[j]] += delta, v[j] -= delta;
else minv[j] -= delta;
j0 = j1;
} while (p[j0] != 0);
do { // augment along the found path
int j1 = way[j0];
p[j0] = p[j1];
j0 = j1;
} while (j0);
}
vector<int> assignment(n + 1, 0);
for (int j = 1; j <= m; j++)
if (p[j]) assignment[p[j]] = j;
return {-v[0], assignment};
}// more matchings & flows