Content deleted Content added
Line 156:
/**
* @brief Checks if b < a
*
* Sets a = min(a, b)
* @param a The first parameter to check
* @param b The second parameter to check
* @tparam The type to perform the check on
* @return true if b < a
*/
template <typename T>
constexpr bool ckmin(T& a, const T& b) {
return b < a ? a = b,
}
/**
* @brief Performs the Hungarian algorithm.
*
* Given J jobs and W workers (J <= W), computes the minimum cost to assign each
* prefix of jobs to distinct workers.
Line 195 ⟶ 202:
Vector<T> minTo(W + 1, inf);
Vector<int> prv(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
const int j = job[wCur];
T delta = inf;
Line 205 ⟶ 212:
if (ckmin(minTo[w], C[j][w] - ys[j] - yt[w]))
prv[w] = wCur;
if (ckmin(delta, minTo[w]))
wNext = w;
}
}
Line 230 ⟶ 238:
/**
* @brief Performs a sanity check for the Hungarian algorithm.
*
* Sanity check: https://en.wikipedia.org/wiki/Hungarian_algorithm#Example
* First job (5):
Line 243 ⟶ 253:
void sanityCheckHungarian() {
Vector<Vector<int>> costs{{8, 5, 9}, {4, 2, 4}, {7, 3, 8}};
assert((hungarian(costs) ==
std::println(stderr, "Sanity check passed.");
}
/**
*/
void cordonBleu() {
int N;
Line 275 ⟶ 287:
}
/**
* @brief Entry point into the program.
*
* @return The return code of the program.
*/
int main() {
sanityCheckHungarian();
| |||