Hungarian algorithm: Difference between revisions

Revision as of 15:19, 20 April 2025

Latest revision as of 15:38, 23 May 2025

(4 intermediate revisions by 4 users not shown)

Line 148:

*/

#includeimport <cassert>;

import std;

template <typename T, typename U>

using Pair = std::pair;

using VectorPair = std::vectorpair<T, U>;

template <typename T>

using PairVector = std::pairvector<T>;

template <typename T>

using NumericLimits = std::numeric_limits<T>;

/**

Line 195 ⟶ 200:

// -yt[W] will equal the sum of all deltas

Vector<T> answers;

const T inf = std::numeric_limitsNumericLimits<T>::max();

for (int jCur = 0; jCur < J; ++jCur) { // assign jCur-th job

int wCur = W;

Line 201 ⟶ 206:

// min reduced cost over edges from Z to worker w

Vector<T> minTo(W + 1, inf);

Vector<int> prvprev(W + 1, -1); // previous worker on alternating path

Vector<bool> inZ(W + 1); // whether worker is in Z

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

Line 211 ⟶ 216:

if (!inZ[w]) {

if (ckmin(minTo[w], C[j][w] - ys[j] - yt[w]))

prvprev[w] = wCur;

if (ckmin(delta, minTo[w]))

wNext = w;

Line 231 ⟶ 236:

// update assignments along alternating path

for (int w; wCur != W; wCur = w)

job[wCur] = job[w = prvprev[wCur]];

answers.push_back(-yt[W]);

}

Line 268 ⟶ 273:

Vector<Pair<int, int>> bottles(N);

Vector<Pair<int, int>> couriers(M);

for (const Pair<int, int>& b : bottles)

std::cin >> b.first >> b.second;

for (const Pair<int, int>& c : couriers)

std::cin >> c.first >> c.second;

Pair<int, int> rest;

Line 332 ⟶ 337:

Vector<T> answers;

T ansCur = 0;

const T inf = std::numeric_limitsNumericLimits<T>::max();

// assign jCur-th job using Dijkstra with potentials

for (int jCur = 0; jCur < J; ++jCur) {

int wCur = W; // unvisited worker with minimum distance

job[wCur] = j_curjCur;

Vector<T> dist(W + 1, inf); // Johnson-reduced distances

dist[W] = 0;

Vector<bool> vis(W + 1); // whether visited yet

Vector<int> prvprev(W + 1, -1); // previous worker on shortest path

while (job[wCur] != -1) { // Dijkstra step: pop min worker from heap

T minDist = inf;

Line 355 ⟶ 360:

}

if (ckmin(dist[w], dist[wCur] + edge))

prvprev[w] = wCur;

if (ckmin(minDist, dist[w]))

wNext = w;

}

}

w_curwCur = w_nextwNext;

}

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

Line 368 ⟶ 373:

ans_cur += h[wCur];

for (int w; wCur != W; wCur = w)

job[wCur] = job[w = prvprev[wCur]];

answers.push_back(ansCur);

}

Line 565 ⟶ 570:

If the number of starred zeros is {{mvar|n}} (or in the general case <math>min(n,m)</math>, where {{mvar|n}} is the number of people and {{mvar|m}} is the number of jobs), the algorithm terminates. See the [[#Result|Result]] subsection below on how to interpret the results.

Otherwise, find the lowest uncovered value. Subtract this from every unmarkeduncovered element and add it to every element covered by two lines. Go back to step 4.

This is equivalent to subtracting a number from all rows which are not covered and adding the same number to all columns which are covered. These operations do not change optimal assignments.