src/graph/nf/hungarian/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../util/alias/others/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | // Given J jobs and W workers ($J\leq W$), computes the minimum cost to assign each prefix of jobs to distinct workers. | ||
| 8 | // @tparam T a type large enough to represent integers on the order of $J\max(|g|)$ | ||
| 9 | // @param g a matrix of dimensions JxW such that g[j][w] = cost to assign j-th job to w-th worker (possibly negative) | ||
| 10 | // @return a vector of length J, with the j-th entry equaling the minimum cost to assign the first (j+1) jobs to distinct workers | ||
| 11 | // Time: $O(J^2W)$ | ||
| 12 | template <class T> | ||
| 13 | 18 | CEXP vec<T> hungarian(vvec<T> CR g, T INF = std::numeric_limits<T>::max()) NE { | |
| 14 | 18 | cu32 J = (u32)g.size(), W = (u32)g[0].size(); | |
| 15 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 18 times.
|
18 | assert(J <= W); |
| 16 | 18 | vecu job(W + 1, -1_u32); | |
| 17 | 54 | vec<T> ys(J), yt(W + 1), ret; | |
| 18 |
2/2✓ Branch 2 taken 530 times.
✓ Branch 3 taken 18 times.
|
548 | flt_ (u32, j_now, 0, J) { |
| 19 | 530 | u32 w_now = W; | |
| 20 | 530 | job[w_now] = j_now; | |
| 21 | 1060 | vec<T> min_to(W + 1, INF); | |
| 22 | 530 | vecu prv(W + 1, -1_u32); | |
| 23 | 530 | vecb vis(W + 1); | |
| 24 |
2/2✓ Branch 1 taken 2362 times.
✓ Branch 2 taken 530 times.
|
2892 | while (~job[w_now]) { |
| 25 | 2362 | vis[w_now] = true; | |
| 26 | 2362 | cu32 j = job[w_now]; | |
| 27 | 2362 | u32 w_nxt = -1_u32; | |
| 28 | 2362 | T _ = INF; | |
| 29 |
2/2✓ Branch 0 taken 87375 times.
✓ Branch 1 taken 2362 times.
|
89737 | flt_ (u32, w, 0, W) |
| 30 |
2/2✓ Branch 2 taken 70799 times.
✓ Branch 3 taken 16576 times.
|
87375 | if (!vis[w]) { |
| 31 |
2/2✓ Branch 5 taken 31059 times.
✓ Branch 6 taken 39740 times.
|
70799 | if (min_to[w] > g[j][w] - ys[j] - yt[w]) min_to[w] = g[j][w] - ys[j] - yt[w], prv[w] = w_now; |
| 32 |
2/2✓ Branch 1 taken 8440 times.
✓ Branch 2 taken 62359 times.
|
70799 | if (_ > min_to[w]) _ = min_to[w_nxt = w]; |
| 33 | } | ||
| 34 |
2/2✓ Branch 0 taken 89737 times.
✓ Branch 1 taken 2362 times.
|
92099 | flt_ (u32, w, 0, W + 1) { |
| 35 |
2/2✓ Branch 2 taken 18938 times.
✓ Branch 3 taken 70799 times.
|
89737 | if (vis[w]) ys[job[w]] += _, yt[w] -= _; |
| 36 | 70799 | else min_to[w] -= _; | |
| 37 | } | ||
| 38 | 2362 | w_now = w_nxt; | |
| 39 | } | ||
| 40 |
5/6✓ Branch 3 taken 1529 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 999 times.
✓ Branch 7 taken 530 times.
✓ Branch 8 taken 999 times.
✓ Branch 9 taken 530 times.
|
1529 | for (u32 w; ~w_now && ~prv[w_now]; w_now = w) job[w_now] = job[w = prv[w_now]]; |
| 41 | 530 | ret.push_back(-yt[W]); | |
| 42 | } | ||
| 43 | 18 | return ret; | |
| 44 | 18 | } | |
| 45 | |||
| 46 | } // namespace tifa_libs | ||
| 47 |