Hungarian algorithm: Difference between revisions

Revision as of 00:11, 28 March 2025

Revision as of 15:08, 20 April 2025

Line 149:

#include <cassert>

#include <iostream>

import std;

#include <limits>

#include <vector>

using namespacePair = std::pair;

using Vector = std::vector;

/**

Line 158 ⟶ 159:

* @return true if b < a

*/

template <classtypename T>
bool ckmin(T & a, const T & b) {
return b < a ? a = b, 1 : 0;
}

/**

Line 172 ⟶ 176:

* to assign the first (j+1) jobs to distinct workers

*/

template <typename T>

template <class T> vectorVector<T> hungarian(const vectorVector<vectorVector<T>>& &C) {

const int J = (static_cast<int)size>(C), W = .size(int)size(C[0]);

const int W = static_cast<int>(C[0].size());

assert(J <= W);

// job[w] = job assigned to w-th worker, or -1 if no job assigned

// note: a W-th worker was added for convenience

vectorVector<int> job(W + 1, -1);

vectorVector<T> ys(J),;
Vector<T> yt(W + 1); // potentials

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

vectorVector<T> answers;

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

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

int w_curwCur = W;

job[w_curwCur] = j_curjCur;

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

vectorVector<T> min_tominTo(W + 1, inf);

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

vectorVector<bool> in_ZinZ(W + 1); // whether worker is in Z

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

in_Z[w_curwCur] = true;

const int j = job[w_curwCur];

T delta = inf;

int w_nextwNext;

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

if (!in_ZinZ[w]) {

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

prv[w] = w_curwCur;

if (ckmin(delta, min_tominTo[w])) w_nextwNext = w;

}

}

// delta will always be nonnegative,

// except possibly during the first time this loop runs

// if any entries of C[j_curjCur] are negative

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

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

else min_to ys[job[w]] -+= delta;

yt[w] -= delta;

} else {

minTo[w] -= delta;

}

}

w_curwCur = w_nextwNext;

}

// update assignments along alternating path

for (int w; w_curwCur != W; w_curwCur = w)
job[w_curwCur] = job[w = prv[w_curwCur]];

answers.push_back(-yt[W]);

}

Line 229 ⟶ 241:

* wash windows: Bob -> 3

*/

void sanity_check_hungariansanityCheckHungarian() {

vectorVector<vectorVector<int>> costs{{8, 5, 9}, {4, 2, 4}, {7, 3, 8}};

assert((hungarian(costs) == vector<int>{5, 9, 15}));

cerr <<std::println(stderr, "Sanity check passed.\n");

}

// solves https://open.kattis.com/problems/cordonbleu

void cordon_bleucordonBleu() {

int N, M;

cin >> N >>int M;

vector<pair<int,std::cin int>> B(N), C(>> M);

vectorVector<pairPair<int, int>> bottlesB(N), couriers(M);

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

for (auto &b : bottles) cin >> b.first >> b.second;

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

for (auto &c : couriers) cin >> c.first >> c.second;

pairVector<Pair<int, int>> restcouriers(M);

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

cin >> rest.first >> rest.second;

for (auto &b : bottles) std::cin >> b.first >> b.second;

vector<vector<int>> costs(N, vector<int>(N + M - 1));

autofor dist(const = [&](pairPair<int, int>& x,c pair<int, int>: ycouriers) {

returnstd::cin abs(x.first>> - yc.first) + abs(x.second ->> yc.second);

Pair<int, int> rest;

for (auto &c std:: couriers) cin >> crest.first >> crest.second;

vectorVector<vectorVector<int>> costs(N, vectorVector<int>(N + M - 1));

auto dist = [&](const Pair<int, int>& x, const Pair<int, int>& y) -> int {

return std::abs(x.first - y.first) + std::abs(x.second - y.second);

};

for (int b = 0; b < N; ++b) {

for (int c = 0; c < M; ++c) { // courier -> bottle -> restaurant

costs[b][c] = dist(couriers[c], bottles[b]) + dist(bottles[b], rest);

for (int _ = 0; _ < N - 1; ++_) { // restaurant -> bottle -> restaurant

dist(couriers[c], bottles[b]) + dist(bottles[b], rest);

}

for (int _ = 0; _ < N - 1; ++_) { // restaurant -> bottle -> restaurant

costs[b][_ + M] = 2 * dist(bottles[b], rest);

}

}

cout << std::println(hungarian(costs).back() << "\n");

}

int main() {

sanity_check_hungariansanityCheckHungarian();

cordon_bleucordonBleu();

}

</syntaxhighlight>