src/graph/min_cycle_mean/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 T> | ||
| 9 | 10 | CEXP T min_cycle_mean(vec<edge_t<T>> CR edges, u32 n, T INF = inf_v<T>) NE { | |
| 10 | 30 | vec<T> d(n + 1), d2(n + 1); | |
| 11 |
2/2✓ Branch 1 taken 18210 times.
✓ Branch 2 taken 10 times.
|
18220 | for (u32 i = 0; i < n; ++i, std::swap(d, d2)) |
| 12 |
2/2✓ Branch 11 taken 165267000 times.
✓ Branch 12 taken 18210 times.
|
165285210 | for (fill_n(begin(d), n, INF); auto [w, u, v] : edges) d[v] = min(d[v], d2[u] + w); |
| 13 | 20 | vec<T> dn = d2, mx(n + 1); | |
| 14 | 10 | T ans = INF; | |
| 15 | 18230 | transform(dn, begin(mx), [&](auto x) NE { return x / n; }); | |
| 16 | 10 | fill(d2, 0); | |
| 17 |
2/2✓ Branch 1 taken 18200 times.
✓ Branch 2 taken 10 times.
|
18210 | for (u32 i = 1; i < n; ++i, std::swap(d, d2)) { |
| 18 |
2/2✓ Branch 11 taken 165200000 times.
✓ Branch 12 taken 18200 times.
|
165218200 | for (fill_n(begin(d), n, INF); auto [w, u, v] : edges) d[v] = min(d[v], d2[u] + w); |
| 19 |
2/2✓ Branch 5 taken 48038200 times.
✓ Branch 6 taken 18200 times.
|
48056400 | flt_ (u32, j, 0, n) mx[j] = max(mx[j], (dn[j] - d[j]) / (n - i)); |
| 20 | } | ||
| 21 |
2/2✓ Branch 0 taken 18210 times.
✓ Branch 1 taken 10 times.
|
18220 | flt_ (u32, i, 0, n) |
| 22 |
2/2✓ Branch 1 taken 18200 times.
✓ Branch 2 taken 10 times.
|
18210 | if (dn[i] < INF) ans = min(ans, mx[i]); |
| 23 | 20 | return ans; | |
| 24 | 10 | } | |
| 25 | |||
| 26 | } // namespace tifa_libs | ||
| 27 |