src/graph/nf/hlpp/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../util/alias/others/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | template <class T = u32> | ||
| 8 | class hlpp { | ||
| 9 | static CEXP u32 inf = 0x3f3f3f3f; | ||
| 10 | struct TIFA { | ||
| 11 | u32 to; | ||
| 12 | T w, inv; | ||
| 13 | }; | ||
| 14 | vecu h, gap; | ||
| 15 | cu32 n, s, t; | ||
| 16 | u32 level{0}; | ||
| 17 | vvecu B; | ||
| 18 | |||
| 19 | 3989 | CEXP u32 select() NE { | |
| 20 |
6/6✓ Branch 0 taken 6060 times.
✓ Branch 1 taken 37 times.
✓ Branch 4 taken 2108 times.
✓ Branch 5 taken 3952 times.
✓ Branch 6 taken 2108 times.
✓ Branch 7 taken 3989 times.
|
6097 | while (~level && B[level].empty()) --level; |
| 21 |
2/2✓ Branch 0 taken 3952 times.
✓ Branch 1 taken 37 times.
|
3989 | retif_((~level), B[level].back(), 0); |
| 22 | } | ||
| 23 | |||
| 24 | public: | ||
| 25 | vvec<TIFA> e; | ||
| 26 | vec<T> exf; | ||
| 27 | |||
| 28 | 240 | CEXP hlpp(u32 n, u32 s, u32 t) NE : n{n}, s{s}, t{t}, B(n), e(n), exf(n + 1) {} | |
| 29 | |||
| 30 | 9145 | CEXP pttu add(u32 u, u32 v, T w, T rw = 0) NE { | |
| 31 | 9145 | cu32 lstu = (u32)e[u].size(), lstv = (u32)e[v].size(); | |
| 32 | 9145 | e[u].push_back({v, w, lstv}), e[v].push_back({u, rw, lstu}); | |
| 33 | 9145 | return {u, e[u].size() - 1}; | |
| 34 | } | ||
| 35 | 40 | T get() NE { | |
| 36 |
2/2✓ Branch 1 taken 3 times.
✓ Branch 2 taken 37 times.
|
40 | if (!bfs_init()) return 0; |
| 37 | 37 | gap = vecu(n, 0); | |
| 38 |
2/2✓ Branch 0 taken 2131 times.
✓ Branch 1 taken 37 times.
|
2168 | flt_ (u32, i, 0, n) |
| 39 |
2/2✓ Branch 1 taken 2120 times.
✓ Branch 2 taken 11 times.
|
2131 | if (h[i] != inf) ++gap[h[i]]; |
| 40 | 37 | h[s] = n, push(s); | |
| 41 | u32 u; | ||
| 42 |
2/2✓ Branch 1 taken 3952 times.
✓ Branch 2 taken 37 times.
|
4026 | while ((u = select())) |
| 43 |
2/2✓ Branch 3 taken 1405 times.
✓ Branch 4 taken 2547 times.
|
3952 | if (B[level].pop_back(); push(u)) { |
| 44 |
2/2✓ Branch 2 taken 51 times.
✓ Branch 3 taken 1354 times.
|
1405 | if (!--gap[h[u]]) |
| 45 |
2/2✓ Branch 0 taken 4050 times.
✓ Branch 1 taken 51 times.
|
4101 | flt_ (u32, i, 0, n) |
| 46 |
8/8✓ Branch 0 taken 3999 times.
✓ Branch 1 taken 51 times.
✓ Branch 4 taken 1754 times.
✓ Branch 5 taken 2245 times.
✓ Branch 7 taken 1091 times.
✓ Branch 8 taken 663 times.
✓ Branch 9 taken 1091 times.
✓ Branch 10 taken 2959 times.
|
4050 | if (i != s && h[i] > h[u] && h[i] < n + 1) h[i] = n + 1; |
| 47 | 1405 | relabel(u); | |
| 48 | } | ||
| 49 | 37 | return exf[t]; | |
| 50 | } | ||
| 51 | |||
| 52 | private: | ||
| 53 | 40 | bool bfs_init() NE { | |
| 54 | 40 | h = vecu(n, inf), h[t] = 0; | |
| 55 | 80 | std::queue<u32> q({t}); | |
| 56 |
2/2✓ Branch 1 taken 2198 times.
✓ Branch 2 taken 40 times.
|
2238 | while (!q.empty()) { |
| 57 | 2198 | cu32 u = q.front(); | |
| 58 |
2/2✓ Branch 7 taken 18185 times.
✓ Branch 8 taken 2198 times.
|
20383 | for (q.pop(); auto [to, w, lstv] : e[u]) |
| 59 |
6/6✓ Branch 2 taken 9030 times.
✓ Branch 3 taken 9155 times.
✓ Branch 6 taken 2158 times.
✓ Branch 7 taken 6872 times.
✓ Branch 8 taken 2158 times.
✓ Branch 9 taken 16027 times.
|
18185 | if (e[to][lstv].w && h[to] > h[u] + 1) h[to] = h[u] + 1, q.push(to); |
| 60 | } | ||
| 61 | 40 | return h[s] != inf; | |
| 62 | 40 | } | |
| 63 | 3989 | CEXP bool push(u32 u) NE { | |
| 64 |
2/2✓ Branch 6 taken 23234 times.
✓ Branch 7 taken 1442 times.
|
24676 | for (const bool init = u == s; auto& [to, w, lstv] : e[u]) { |
| 65 |
10/10✓ Branch 0 taken 16239 times.
✓ Branch 1 taken 6995 times.
✓ Branch 2 taken 16098 times.
✓ Branch 3 taken 141 times.
✓ Branch 6 taken 3433 times.
✓ Branch 7 taken 12665 times.
✓ Branch 9 taken 1 time.
✓ Branch 10 taken 3573 times.
✓ Branch 11 taken 19661 times.
✓ Branch 12 taken 3573 times.
|
23234 | if (!w || (!init && h[u] != h[to] + 1) || h[to] == inf) continue; |
| 66 |
2/2✓ Branch 0 taken 140 times.
✓ Branch 1 taken 3433 times.
|
3573 | T k = init ? w : min(w, exf[u]); |
| 67 |
7/8✓ Branch 0 taken 3573 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 3405 times.
✓ Branch 3 taken 168 times.
✓ Branch 5 taken 2606 times.
✓ Branch 6 taken 799 times.
✓ Branch 7 taken 2606 times.
✓ Branch 8 taken 967 times.
|
3573 | if (to != s && to != t && !exf[to]) B[h[to]].push_back(to), level = max(level, h[to]); |
| 68 |
2/2✓ Branch 5 taken 2547 times.
✓ Branch 6 taken 1026 times.
|
3573 | if (exf[u] -= k, exf[to] += k, w -= k, e[to][lstv].w += k; !exf[u]) return false; |
| 69 | } | ||
| 70 | 1442 | return true; | |
| 71 | } | ||
| 72 | 1405 | CEXP void relabel(u32 u) NE { | |
| 73 |
2/2✓ Branch 7 taken 11311 times.
✓ Branch 8 taken 1405 times.
|
12716 | for (h[u] = inf; auto [to, w, _] : e[u]) |
| 74 |
2/2✓ Branch 0 taken 6946 times.
✓ Branch 1 taken 4365 times.
|
11311 | if (w) h[u] = min(h[u], h[to]); |
| 75 |
2/2✓ Branch 1 taken 1346 times.
✓ Branch 2 taken 59 times.
|
1405 | if (++h[u] < n) B[h[u]].push_back(u), level = max(level, h[u]), ++gap[h[u]]; |
| 76 | 1405 | } | |
| 77 | }; | ||
| 78 | |||
| 79 | } // namespace tifa_libs | ||
| 80 |