Hungarian algorithm: Difference between revisions

Revision as of 02:43, 14 May 2023

Revision as of 03:08, 14 May 2023

Line 126:

===Implementation in C++===

For convenience of implementation, the code below adds an additional worker <math>w_{W}</math> such that <math>y(w_{W})</math> stores the negation of the sum of all <math>\Delta</math> computed so far. After the <math>j</math>th job is added and the matching updated, the cost of the current matching equals the sum of all <math>\Delta</math> computed so far, or <math>-y(w_{W})</math>.<syntaxhighlight lang="cpp" line="1">

This code is adapted from e-maxx :: algo.<ref>{{cite web

| url = http://e-maxx.ru/algo/assignment_hungary#6

| title = Hungarian Algorithm for Solving the Assignment Problem

| author = <!--Not stated-->

| date = August 23, 2012

| website = e-maxx :: algo

| access-date = May 13, 2023

}}</ref>

<syntaxhighlight lang="cpp" line="1">

/**

* Solution to https://open.kattis.com/problems/cordonbleu using Hungarian

* algorithm.

* Based on https://github.com/mpfeifer1/Kattis/blob/master/cordonbleu.cpp

*/

Line 170 ⟶ 181:

int w_cur = W;

job[w_cur] = j_cur;

// minimummin reduced cost over edges enteringfrom Z to worker w

vector<T> distmin_to(W + 1, inf);

vector<int> prv(W + 1, -1); // forprevious restoringworker on alternating path

vector<bool> visin_Z(W + 1); // whether worker is in Z

while (job[w_cur] != -1) { // runs at most j_cur + 1 times

visin_Z[w_cur] = true;

const int j = job[w_cur];

T delta = inf;

int w_next;

for (int w = 0; w < W; ++w) {

if (!visin_Z[w]) {

if (ckmin(distmin_to[w], C[j][w] - ys[j] - yt[w])) prv[w] = w_cur;

if (ckmin(delta, dist prv[w])) w_next = ww_cur;

if (ckmin(delta, min_to[w])) w_next = w;

}

}

Line 189 ⟶ 201:

// negative

for (int w = 0; w <= W; ++w) {

if (visin_Z[w]) ys[job[w]] += delta, yt[w] -= delta;

else distmin_to[w] -= delta;

}

w_cur = w_next;