src/graph/nf/ssp/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../util/alias/others/lib.hpp" | ||
| 4 | #include "../../../util/traits/math/lib.hpp" | ||
| 5 | |||
| 6 | namespace tifa_libs { | ||
| 7 | |||
| 8 | template <class W = u32, class C = i32> | ||
| 9 | class ssp { | ||
| 10 | struct TIFA { | ||
| 11 | u32 to, inv; | ||
| 12 | W w; | ||
| 13 | C c; | ||
| 14 | }; | ||
| 15 | cu32 N, S, T; | ||
| 16 | vec<W> flow; | ||
| 17 | vecptu pre; | ||
| 18 | |||
| 19 | template <class EW> | ||
| 20 | 177 | bool sssp(EW inflow) NE { | |
| 21 | using SW = std::make_signed_t<EW>; | ||
| 22 | 354 | vec<SW> dis(N, inf_v<SW>); | |
| 23 | 177 | vecb inq(N); | |
| 24 | 354 | std::queue<u32> q({S}); | |
| 25 | 177 | dis[S] = 0, flow[S] = W(inflow), flow[T] = 0, inq[S] = true; | |
| 26 |
2/2✓ Branch 1 taken 18924 times.
✓ Branch 2 taken 177 times.
|
19101 | while (!q.empty()) { |
| 27 | 18924 | cu32 u = q.front(); | |
| 28 | 18924 | q.pop(), inq[u] = false; | |
| 29 |
2/2✓ Branch 2 taken 318028 times.
✓ Branch 3 taken 18924 times.
|
336952 | flt_ (u32, i, 0, (u32)e[u].size()) |
| 30 |
6/6✓ Branch 4 taken 156870 times.
✓ Branch 5 taken 161158 times.
✓ Branch 6 taken 28050 times.
✓ Branch 7 taken 128820 times.
✓ Branch 8 taken 28050 times.
✓ Branch 9 taken 289978 times.
|
318028 | if (auto v = e[u][i]; dis[u] + v.c < dis[v.to] && v.w) { |
| 31 |
2/2✓ Branch 4 taken 18747 times.
✓ Branch 5 taken 9303 times.
|
28050 | if (dis[v.to] = dis[u] + v.c; !inq[v.to]) q.push(v.to), inq[v.to] = 1; |
| 32 | 28050 | flow[v.to] = min(flow[u], v.w), pre[v.to] = {u, i}; | |
| 33 | } | ||
| 34 | } | ||
| 35 | 177 | return flow[T]; | |
| 36 | 177 | } | |
| 37 | template <class EW, class EC> | ||
| 38 | 145 | CEXP void update(EW& retflow, EC& retcost) NE { | |
| 39 | 145 | retflow += flow[T]; | |
| 40 |
2/2✓ Branch 0 taken 746 times.
✓ Branch 1 taken 145 times.
|
891 | for (u32 u = T; u != S; u = pre[u].first) { |
| 41 | 746 | e[pre[u].first][pre[u].second].w -= flow[T]; | |
| 42 | 746 | e[u][e[pre[u].first][pre[u].second].inv].w += flow[T]; | |
| 43 | 746 | retcost += EC(flow[T]) * e[pre[u].first][pre[u].second].c; | |
| 44 | } | ||
| 45 | 145 | } | |
| 46 | |||
| 47 | public: | ||
| 48 | vvec<TIFA> e; | ||
| 49 | |||
| 50 | 192 | CEXP ssp(u32 n, u32 s, u32 t) NE : N{n}, S{s}, T{t}, flow(n), pre(n), e(n) {} | |
| 51 | |||
| 52 | 10324 | CEXP void add(u32 u, u32 v, cT_(W) w, cT_(C) c) NE { | |
| 53 | 10324 | cu32 lu = u32(e[u].size()), lv = u32(e[v].size()); | |
| 54 | 10324 | e[u].push_back({v, lv, w, c}), e[v].push_back({u, lu, 0, -c}); | |
| 55 | 10324 | } | |
| 56 | template <class EW = u64, class EC = i64> | ||
| 57 | 32 | CEXP std::pair<EW, EC> get(EW inflow = std::numeric_limits<EW>::max()) NE { | |
| 58 | 32 | EW retflow = 0; | |
| 59 | 32 | EC retcost = 0; | |
| 60 | 32 | const bool flag = inflow == std::numeric_limits<W>::max(); | |
| 61 |
3/4✗ Branch 1 not taken.
✓ Branch 2 taken 177 times.
✓ Branch 4 taken 145 times.
✓ Branch 5 taken 32 times.
|
177 | while (sssp(flag ? inflow : inflow - retflow)) update(retflow, retcost); |
| 62 | 32 | return {retflow, retcost}; | |
| 63 | } | ||
| 64 | }; | ||
| 65 | |||
| 66 | } // namespace tifa_libs | ||
| 67 |