src/graph/mst/cle/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../ds/dsu/basic/lib.hpp" | ||
| 4 | #include "../../../ds/heap/skew/lib.hpp" | ||
| 5 | |||
| 6 | namespace tifa_libs { | ||
| 7 | |||
| 8 | template <class T> | ||
| 9 | 37 | CEXP vec<edge_t<T>> cle(u32 n, u32 root, vec<edge_t<T>> CR arcs) NE { | |
| 10 | 37 | skew_heap<T> heap; | |
| 11 | 37 | dsu_basic uf(n); | |
| 12 | 148 | vecu used(n, -1_u32), from(n), come(n, -1_u32); | |
| 13 | 37 | vec<T> from_cost(n); | |
| 14 | 37 | used[root] = root; | |
| 15 | 74 | vecu par_e(arcs.size(), -1_u32), stem(n, -1_u32), idxs; | |
| 16 |
2/2✓ Branch 1 taken 1804364 times.
✓ Branch 2 taken 37 times.
|
1804401 | flt_ (u32, i, 0, (u32)arcs.size()) { |
| 17 | 1804364 | auto [w, u, v] = arcs[i]; | |
| 18 | 1804364 | come[v] = heap.push(come[v], w, i); | |
| 19 | } | ||
| 20 | 37 | T costs = 0; | |
| 21 |
3/4✓ Branch 1 taken 951182 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 1514644 times.
✓ Branch 4 taken 37 times.
|
2465863 | flt_ (u32, start, 0, n) { |
| 22 |
2/2✓ Branch 1 taken 563462 times.
✓ Branch 2 taken 951182 times.
|
1514644 | if (~used[start]) continue; |
| 23 | 951182 | u32 now = start, cyc = 0; | |
| 24 | 951182 | vecu chi_e; | |
| 25 |
6/6✓ Branch 1 taken 954225 times.
✓ Branch 2 taken 1514607 times.
✓ Branch 4 taken 3043 times.
✓ Branch 5 taken 951182 times.
✓ Branch 6 taken 1517650 times.
✓ Branch 7 taken 951182 times.
|
2468832 | while (!~used[now] || used[now] == start) { |
| 26 | 1517650 | used[now] = start; | |
| 27 | 1517650 | auto& node = heap.d[come[now]]; | |
| 28 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 1517650 times.
|
1517650 | if (!~come[now]) return {}; |
| 29 | 1517650 | u32 src = (u32)uf.find(arcs[node.idx].u); | |
| 30 | 1517650 | T cost = heap.weight(come[now]); | |
| 31 | 1517650 | u32 idx = node.idx; | |
| 32 |
2/2✓ Branch 3 taken 1065 times.
✓ Branch 4 taken 1516585 times.
|
1517650 | if (come[now] = heap.pop(come[now]); src == now) continue; |
| 33 |
2/2✓ Branch 3 taken 1514607 times.
✓ Branch 4 taken 1978 times.
|
1516585 | if (from[now] = src, from_cost[now] = cost; !~stem[now]) stem[now] = idx; |
| 34 | 1516585 | costs += cost, idxs.push_back(idx); | |
| 35 |
2/2✓ Branch 3 taken 11503 times.
✓ Branch 4 taken 1516585 times.
|
1528088 | while (cyc) par_e[chi_e.back()] = idx, chi_e.pop_back(), --cyc; |
| 36 |
2/2✓ Branch 2 taken 1978 times.
✓ Branch 3 taken 1514607 times.
|
1516585 | if (chi_e.push_back(idx); used[src] == start) { |
| 37 | 1978 | u32 p = now; | |
| 38 | do { | ||
| 39 |
2/2✓ Branch 1 taken 11199 times.
✓ Branch 2 taken 304 times.
|
11503 | if (~come[p]) heap.apply(come[p], -from_cost[p]); |
| 40 |
2/2✓ Branch 0 taken 9525 times.
✓ Branch 1 taken 1978 times.
|
11503 | if (p != now) { |
| 41 | 9525 | uf.merge(p, now); | |
| 42 | 9525 | u32 newheap = heap.merge(come[now], come[p]); | |
| 43 | 9525 | come[now = (u32)uf.find(now)] = newheap; | |
| 44 | } | ||
| 45 | 11503 | p = (u32)uf.find(from[p]), ++cyc; | |
| 46 |
2/2✓ Branch 0 taken 9525 times.
✓ Branch 1 taken 1978 times.
|
11503 | } while (p != now); |
| 47 | 1514607 | } else now = src; | |
| 48 | } | ||
| 49 | } | ||
| 50 | 37 | vecu vis_e(arcs.size()); | |
| 51 | 37 | vec<edge_t<T>> res; | |
| 52 |
2/2✓ Branch 1 taken 1516585 times.
✓ Branch 2 taken 37 times.
|
1516622 | for (u32 _ = (u32)idxs.size(); _--;) { |
| 53 | 1516585 | cu32 i = idxs[_]; | |
| 54 |
2/2✓ Branch 1 taken 1978 times.
✓ Branch 2 taken 1514607 times.
|
1516585 | if (vis_e[i]) continue; |
| 55 | 1514607 | auto [w, u, v] = arcs[i]; | |
| 56 | 1514607 | res.push_back(arcs[i]); | |
| 57 | 1514607 | u32 x = stem[v]; | |
| 58 |
2/2✓ Branch 2 taken 1978 times.
✓ Branch 3 taken 1514607 times.
|
1516585 | while (x != i) vis_e[x] = true, x = par_e[x]; |
| 59 | } | ||
| 60 | 37 | return res; | |
| 61 | 37 | } | |
| 62 | |||
| 63 | } // namespace tifa_libs | ||
| 64 |