src/graph/blossom/u/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../util/alias/others/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | //! 1-indexed, [1, n] | ||
| 8 | class blossom { | ||
| 9 | u32 n; | ||
| 10 | vvecu g; | ||
| 11 | vecu mate, first; | ||
| 12 | vecb white; | ||
| 13 | vecptu label; | ||
| 14 | |||
| 15 | public: | ||
| 16 | 12 | CEXPE blossom(u32 n) NE { init(n); } | |
| 17 | |||
| 18 | 12 | CEXP void init(u32 n_) NE { | |
| 19 | 12 | n = n_; | |
| 20 | 24 | g = vvecu(n + 1); | |
| 21 | 24 | mate = first = vecu(n + 1); | |
| 22 | 24 | label = vecptu(n + 1); | |
| 23 | 12 | white = vecb(n + 1); | |
| 24 | 12 | } | |
| 25 | 109302 | CEXP void add_edge(u32 u, u32 v) NE { g[u].push_back(v), g[v].push_back(u); } | |
| 26 | 12 | vecptu operator()() NE { | |
| 27 |
2/2✓ Branch 0 taken 3905 times.
✓ Branch 1 taken 12 times.
|
3917 | flt_ (u32, s, 1, n + 1) |
| 28 |
2/2✓ Branch 1 taken 2354 times.
✓ Branch 2 taken 1551 times.
|
3905 | if (!mate[s]) augment(s); |
| 29 |
2/2✓ Branch 0 taken 3905 times.
✓ Branch 1 taken 12 times.
|
3917 | flt_ (u32, s, 1, n + 1) |
| 30 |
7/8✓ Branch 1 taken 803 times.
✓ Branch 2 taken 3102 times.
✓ Branch 5 taken 715 times.
✓ Branch 6 taken 88 times.
✓ Branch 7 taken 715 times.
✓ Branch 8 taken 3190 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 715 times.
|
3905 | if (!mate[s] && !white[s]) assert(!augment(s)); |
| 31 | 12 | vecptu ans; | |
| 32 |
2/2✓ Branch 0 taken 3905 times.
✓ Branch 1 taken 12 times.
|
3917 | flt_ (u32, s, 1, n + 1) |
| 33 |
2/2✓ Branch 1 taken 1551 times.
✓ Branch 2 taken 2354 times.
|
3905 | if (s < mate[s]) ans.emplace_back(s, mate[s]); |
| 34 | 12 | return ans; | |
| 35 | } | ||
| 36 | |||
| 37 | private: | ||
| 38 |
2/2✓ Branch 3 taken 25852 times.
✓ Branch 4 taken 713 times.
|
26565 | CEXP u32 gf(u32 x) NE { retif_((!white[first[x]]), first[x], first[x] = gf(first[x])); } |
| 39 | 1814 | CEXP void match(u32 p, u32 b) NE { | |
| 40 |
2/2✓ Branch 3 taken 1559 times.
✓ Branch 4 taken 255 times.
|
1814 | if (swap(b, mate[p]); mate[b] != p) return; |
| 41 |
2/2✓ Branch 3 taken 247 times.
✓ Branch 4 taken 8 times.
|
255 | if (auto [k, v] = label[p]; !v) mate[b] = k, match(k, b); |
| 42 | 8 | else match(k, v), match(v, k); | |
| 43 | } | ||
| 44 | 3069 | bool augment(u32 s) NE { | |
| 45 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 3069 times.
|
3069 | assert(s), white[s] = true, first[s] = 0, label[s] = {0, 0}; |
| 46 | 6138 | std::queue<u32> q({s}); | |
| 47 |
2/2✓ Branch 1 taken 5336 times.
✓ Branch 2 taken 1518 times.
|
6854 | while (!q.empty()) { |
| 48 | 5336 | cu32 a = q.front(); | |
| 49 |
2/2✓ Branch 7 taken 15362 times.
✓ Branch 8 taken 3785 times.
|
19147 | for (q.pop(); auto b : g[a]) |
| 50 |
3/4✗ Branch 0 not taken.
✓ Branch 1 taken 15362 times.
✓ Branch 5 taken 5825 times.
✓ Branch 6 taken 9537 times.
|
15362 | if (assert(b); white[b]) { |
| 51 | 5825 | u32 x = gf(a), y = gf(b), lca = 0; | |
| 52 |
4/4✓ Branch 0 taken 992 times.
✓ Branch 1 taken 6284 times.
✓ Branch 2 taken 778 times.
✓ Branch 3 taken 5506 times.
|
7276 | while (x || y) { |
| 53 |
2/2✓ Branch 0 taken 1637 times.
✓ Branch 1 taken 133 times.
|
1770 | if (y) swap(x, y); |
| 54 |
2/2✓ Branch 3 taken 319 times.
✓ Branch 4 taken 1451 times.
|
1770 | if (label[x] == pttu{a, b}) { |
| 55 | 319 | lca = x; | |
| 56 | 319 | break; | |
| 57 | } | ||
| 58 | 1451 | label[x] = {a, b}, x = gf(label[mate[x]].first); | |
| 59 | } | ||
| 60 |
2/2✓ Branch 4 taken 11650 times.
✓ Branch 5 taken 5825 times.
|
17475 | for (u32 v : {gf(a), gf(b)}) |
| 61 |
2/2✓ Branch 0 taken 1101 times.
✓ Branch 1 taken 11650 times.
|
12751 | while (v != lca) { |
| 62 |
1/2✗ Branch 2 not taken.
✓ Branch 3 taken 1101 times.
|
1101 | assert(!white[v]); |
| 63 | 1101 | q.push(v); | |
| 64 | 1101 | white[v] = true, first[v] = lca; | |
| 65 | 1101 | v = gf(label[mate[v]].first); | |
| 66 | } | ||
| 67 |
2/2✓ Branch 1 taken 1551 times.
✓ Branch 2 taken 7986 times.
|
9537 | } else if (!mate[b]) { |
| 68 | 3102 | match(mate[b] = a, b), white = vecb(n + 1); | |
| 69 | 1551 | return true; | |
| 70 |
2/2✓ Branch 3 taken 5717 times.
✓ Branch 4 taken 2269 times.
|
7986 | } else if (!white[mate[b]]) { |
| 71 | 5717 | white[mate[b]] = true; | |
| 72 | 5717 | label[first[mate[b]] = b] = {0, 0}, label[mate[b]] = {a, 0}; | |
| 73 | 5717 | q.push(mate[b]); | |
| 74 | } | ||
| 75 | } | ||
| 76 | 1518 | return false; | |
| 77 | 3069 | } | |
| 78 | }; | ||
| 79 | |||
| 80 | } // namespace tifa_libs | ||
| 81 |