src/graph/mst/steiner/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../ds/heap/radix/lib.hpp" | ||
| 4 | #include "../../../util/traits/math/lib.hpp" | ||
| 5 | #include "../../ds/graph_c/lib.hpp" | ||
| 6 | |||
| 7 | namespace tifa_libs { | ||
| 8 | |||
| 9 | template <bool get_edges, wgraph_c G, class T = TPN G::Et> | ||
| 10 | 24 | auto steiner_tree(G CR g, spnu x, vec<T> CR vw = {}, T INF = inf_v<T>) NE { | |
| 11 | 24 | cu32 n = g.vsize(), k = (u32)x.size(); | |
| 12 | 24 | const bool has_vweight = !vw.empty(); | |
| 13 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
|
24 | if (has_vweight) assert(!uint_c<T>); |
| 14 | 48 | vvec<T> dp(n, vec<T>(1 << k, INF)); | |
| 15 |
2/2✓ Branch 3 taken 178 times.
✓ Branch 4 taken 24 times.
|
202 | flt_ (u32, i, 0, k) dp[x[i]][1 << i] = 0; |
| 16 | 24 | rheap<T, u32> q; | |
| 17 | 92672 | auto dij = [&](u32 s) { | |
| 18 |
2/2✓ Branch 1 taken 6786879 times.
✓ Branch 2 taken 46324 times.
|
6833203 | while (!q.empty()) { |
| 19 | 6786879 | auto [dis, u] = q.top(); | |
| 20 |
2/2✓ Branch 3 taken 2435629 times.
✓ Branch 4 taken 4351250 times.
|
6786879 | if (q.pop(); dp[u][s] != dis) continue; |
| 21 |
2/2✓ Branch 6 taken 113499418 times.
✓ Branch 7 taken 4351250 times.
|
117850668 | for (auto [v, w] : g[u]) |
| 22 |
2/2✓ Branch 2 taken 3401338 times.
✓ Branch 3 taken 110098080 times.
|
113499418 | if (dp[v][s] > dis + w) |
| 23 | 3401338 | q.emplace(dp[v][s] = dis + w, v); | |
| 24 | } | ||
| 25 | }; | ||
| 26 | 24 | std::queue<u32> qw; | |
| 27 | ✗ | auto bm = [&](u32 s) { | |
| 28 | ✗ | vecb inq(n); | |
| 29 | ✗ | while (!qw.empty()) { | |
| 30 | ✗ | cu32 u = qw.front(); | |
| 31 | ✗ | qw.pop(), inq[u] = false; | |
| 32 | ✗ | for (auto [v, w] : g[u]) | |
| 33 | ✗ | if (dp[v][s] > dp[u][s] + w + vw[v]) | |
| 34 | ✗ | if (dp[v][s] = dp[u][s] + w + vw[v]; !inq[v]) inq[v] = true, qw.push(v); | |
| 35 | } | ||
| 36 | ✗ | }; | |
| 37 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 24 times.
|
24 | if (has_vweight) |
| 38 | ✗ | flt_ (u32, s, 1, 1_u32 << k) { | |
| 39 | ✗ | flt_ (u32, i, 0, n) { | |
| 40 | ✗ | for (u32 t = s & (s - 1); t; t = s & (t - 1)) | |
| 41 | ✗ | if (dp[i][s] > dp[i][t] + dp[i][s ^ t] - vw[i]) dp[i][s] = dp[i][t] + dp[i][s ^ t] - vw[i]; | |
| 42 | ✗ | if (dp[i][s] < INF) qw.push(i); | |
| 43 | } | ||
| 44 | ✗ | bm(s); | |
| 45 | } | ||
| 46 | else | ||
| 47 |
2/2✓ Branch 1 taken 46324 times.
✓ Branch 2 taken 24 times.
|
46348 | flt_ (u32, s, 1, 1_u32 << k) { |
| 48 |
2/2✓ Branch 0 taken 3396816 times.
✓ Branch 1 taken 46324 times.
|
3443140 | flt_ (u32, i, 0, n) { |
| 49 |
2/2✓ Branch 0 taken 430620018 times.
✓ Branch 1 taken 3396816 times.
|
434016834 | for (u32 t = s & (s - 1); t; t = s & (t - 1)) |
| 50 |
2/2✓ Branch 6 taken 9341538 times.
✓ Branch 7 taken 421278480 times.
|
430620018 | if (dp[i][s] > dp[i][t] + dp[i][s ^ t]) dp[i][s] = dp[i][t] + dp[i][s ^ t]; |
| 51 |
2/2✓ Branch 2 taken 3385541 times.
✓ Branch 3 taken 11275 times.
|
3396816 | if (dp[i][s] < INF) q.emplace(dp[i][s], i); |
| 52 | } | ||
| 53 | 46324 | dij(s); | |
| 54 | } | ||
| 55 | if CEXP (get_edges) { | ||
| 56 | 24 | vecptu edges; | |
| 57 |
1/2✗ Branch 3 not taken.
✓ Branch 4 taken 24 times.
|
24 | if (dp[x[0]].back() == INF) return std::make_pair(INF, edges); |
| 58 | 24 | u32 pos = 0; | |
| 59 | 24 | T dp_pos = dp[0].back(); | |
| 60 |
2/2✓ Branch 0 taken 1188 times.
✓ Branch 1 taken 24 times.
|
1212 | flt_ (u32, i, 1, n) |
| 61 |
2/2✓ Branch 2 taken 21 times.
✓ Branch 3 taken 1167 times.
|
1188 | if (dp[i].back() < dp_pos) dp_pos = dp[pos = i].back(); |
| 62 | 48 | std::queue<pttu> sp({{(1 << k) - 1, pos}}); | |
| 63 |
2/2✓ Branch 1 taken 332 times.
✓ Branch 2 taken 24 times.
|
356 | while (sp.size()) { |
| 64 | 332 | auto [s, pos] = sp.front(); | |
| 65 | 332 | sp.pop(); | |
| 66 | bool f; | ||
| 67 |
2/2✓ Branch 0 taken 297 times.
✓ Branch 1 taken 332 times.
|
629 | do { |
| 68 |
2/2✓ Branch 6 taken 15876 times.
✓ Branch 7 taken 332 times.
|
16208 | for (f = false; auto [to, w] : g[pos]) |
| 69 |
2/2✓ Branch 4 taken 297 times.
✓ Branch 5 taken 15579 times.
|
15876 | if (dp[to][s] + w == dp[pos][s]) { |
| 70 | 297 | edges.push_back(std::minmax(to, pos)), f = true, pos = to; | |
| 71 | 297 | break; | |
| 72 | } | ||
| 73 | } while (f); | ||
| 74 |
2/2✓ Branch 2 taken 154 times.
✓ Branch 3 taken 178 times.
|
332 | if (dp[pos][s]) |
| 75 |
1/2✓ Branch 0 taken 6422 times.
✗ Branch 1 not taken.
|
6422 | for (u32 t = (s - 1) & s; t; t = (t - 1) & s) |
| 76 |
2/2✓ Branch 6 taken 154 times.
✓ Branch 7 taken 6268 times.
|
6422 | if (dp[pos][t] + dp[pos][s ^ t] == dp[pos][s]) { |
| 77 | 154 | sp.emplace(t, pos), sp.emplace(s ^ t, pos); | |
| 78 | 154 | break; | |
| 79 | } | ||
| 80 | } | ||
| 81 | 24 | return std::make_pair(dp[x[0]].back(), edges); | |
| 82 | 24 | } else return dp[x[0]].back(); | |
| 83 | 24 | } | |
| 84 | |||
| 85 | } // namespace tifa_libs | ||
| 86 |